Designs, graphs and combinatorics in Istanbul

The 3rd Istanbul conference on Design Theory, Graph Theory and Combinatorics took place this week, at Koç University, just north of the city. This is a modern, privately funded university, about ten years old, and already claims to be punching above its weight at research. It is set on top of a hill to the north of the city in the middle of a pine forest; currently very peaceful, but perhaps about to become less so when the third Bosphorus bridge is completed soon.

Koc University

I was a bit hindered by a problem. I had hit my head on a low door lintel in Hay-on-Wye, but had had no ill effects at the time. The following week, I had developed a persistent headache which made sustained mathematical concentration difficult. But while I was in Istanbul, my face swelled up so that vision in my right eye was quite restricted, and my forehead and the side of my face were quite painful, possibly due to internal bleeding. In addition, the wi-fi had serious problems; at the start I couldn’t connect at all, but even when the problems were sorted, I was unable to connect reliably from my room in the guesthouse, since the signal was too poor. So I was maybe not as on-the-ball as usual, and I will just give a fairly short report. Apologies if my Turkish orthography is not always quite right!

On Monday, Marco Buratti gave a talk entitled “Differences may still make a difference”. For me the highlight was that he had used iterated difference set methods to give a fairly simple construction of a 2-ary Steiner system S(2,3,13), that is, a collection of 3-dimensional subspaces in a 13-dimensional vector space over GF(2) with the property that any 2-dimensional space is contained in exactly one of these special 3-subspaces. This design was first found by Braun, Etzion, Østergård, Vardy and Wasserman, and is the only case where a q-ary Steiner system has been constructed! Marco constructed it using a difference family for the Singer cycle: this required 195 base blocks, each of which was required to be a subspace of the vector space. Now he brought in the Frobenius automorphism of order 13, and was able to produce the 195 base blocks from a set of just 15. I think that he was really just using 15 orbits of the group of order 8191.13 generated by the Singer cycle and the Frobenius map.

On Tuesday morning, Doug West began by reminding us of the fact that there exist graphs with arbitrarily high girth and chromatic number; this was first proved by Erdős, an early triumph of the probabilistic method, and explicit algebraic constructions were subseqently given. He and a powerful team of collaborators have given a fairly simple proof of this, using a construction of what they call r-augmented trees (these are regular trees where all non-leaves have valency d, and all leaves are on the same level, with extra edges from each leaf to r vertices on the path to it from the root); these can also be arranged to have high girth. Then an ingenious construction gives the required graph. These augmented trees do other things as well. The downside is that their existence is shown by a double induction which shows that the constructed graphs are impractically large (involving tower functions), because of the double recursion (with one parameter in the exponent on the right-hand side of the recursion) involved in the construction.

In the afternoon, Daniel Horsley addressed the question: for which orders do there exist Steiner triple systems containing no parallel class (set of triples covering each point once) or almost parallel class (set of triples containing each point except one exactly once, and omitting the last point)? He described the situation as it was before 2012, that year in the distant past when he and Darryn Bryant started thinking about the problem. There was one “thin” infinite family, due to Rick Wilson, with no APC, and only finitely many examples with no PC. Here is a brief description of Wilson’s examples, since the method of Bryant and Horsley is an ingenious extension of this. Let n be odd, and take the point set to be the non-zero vectors in an n-dimensional vector space over GF(2); the triples are the sets of three vectors with sum 0. (This is just the projective geometry PG(n−1,2).) The number of points is congruent to 1 mod 3. Now suppose that we can cover all but v by disjoint blocks. The sum of the vectors in each block is zero; so the sum of the vectors in the whole space is v. But it is easy to see that the sum of the vectors in such a vector space of dimension greater than 1 is zero; so v = 0, a contradiction. Anyway, the upshot is that they have another “thin” family of numbers where an STC with no APC exists; but they can do much better for STS with no PC. If p is a prime congruent to 5 (mod 24), then there is such an STS of order 5p+2. The actual construction is even more general, and works for numbers 5n+2 for which every prime divisor p of n has the property that the order of −2 (mod p) is a multiple of 4.

There was a curious sequel. Daniel mentioned that, in the Kaski–Østergård catalogue of over 11 billion STS of order 19, there are just two which fail to have an almost parallel class. Later in the session, Xioa-Nan Lu talked about nexistentially closed graphs (n-e.c. for short), which are graphs where, given any set A of n vertices, and any subset B of A, there is a vertex joined to everything in B and nothing in A\B. (This property, for all n, characterises the countable random graph.) Lu mentioned that the block intersection graph of a Steiner triple system of order v is 3-e.c. only if v is 19 or 21, and that only two systems of order 19 has 3-e.c. block intersection graph: but it is not the same two. So this haystack contains two different pairs of interesting needles!

On Wednesday we were taken on a sightseeing trip to some of the famous sights of the city: the Blue Mosque (Sultan Ahmat’s mosque), Ayasofya (Hagia Sophia, or “holy wisdom”), built by the Romans in about 500 and used as a cathedral for nearly 1000 years and a mosque for the next 500), the Topkapi palace (where as well as sightseeing we had a delicious lunch overlooking the point where the Bosphorus opens out into the Sea of Marmara), and the Grand Bazaar.

Topkapi Palace

The first talk on Thursday was by Ian Wanless, on parity for sets of mutually orthogonal Latin squares. The notion of parity for Latin squares is well understood: a Latin square has three “parities”, the sums of the parities (as permutations) of rows, columns, and symbols respectively; but only two are independent, since the sum of all three is fixed (depending on the congruence of n (mod 4). This explains various things about Latin squares, for example, the fact that the connected components of the intercalate-switching graph or of the bi-embeddability graph tend to have four large components. Ian is extending this to sets of mutually orthogonal Latin squares, that is, for orthogonal arrays with n2 rows and m columns for any m. We would like to know how many “independent” parity bits such a set has. There is an upper bound which is tight for small m (apart from perhaps finitely many exceptions). But the interesting case is that when m = n+1 (corresponding to projective planes), in which case the possible parities seem (on admittedly very limited evidence) to be much more restricted.

Francesca Merola marked the 200th anniversary of the invention of the kaleidoscope with a nice talk on Fano kaleidoscopes. She showed us a picture of Sir David Brewster, one-time Principal of St Andrews, on the lid of an early twentienth-century cigar box.

After lunch, Saieed Akbari talked about the problem of finding orientations of a graph with a forbidden set of out-degrees. Part of its importance arises from the fact that a particular sub-problem is equivalent to Tutte’s 3-flow conjecture for 4-edge-connected graphs.

Kağan Kurşungöz talked about a problem inspired by an attack on the Cerny conjecture for small automata. The problem is to list all isomorphism classes of unary automata (that is, transformations from a set to itself, or mapping patterns) without spending too much time on isomorphism checking. Surely there must be a clever idea for this?

On Friday there was one plenary talk, by Zoltan Füredi, on Turán-type extremal problems for graphs and 3-uniform hypergraphs, whose solutions (or conjectured solutions) are related to designs or finite geometries of some sort: these included C4-free graphs, where the extremal graphs are associated with polarities of projective planes; and 3-hypergraphs with no two pairs of disjoint triples with the same union, where it is conjectured that the 3-subsets of blocks of a Steiner system S(2,5,n) give the extremal example.

After the coffee break, Doğan Bilge gave what for me was one of the real highlights of the conference. He considers relational structures over a finite language. A Fraïssé class is a class of finite structures which is hereditary and satisfies the joint embedding and amalgamation properties. Fraïssé’s famous theorem asserts that for any such class C, there is a unique countable homogeneous structure M (the Fraïssé limit of the class) whose age (collection of finite structures embeddable in M) is C. Now any structure N whose age is contained in C is embeddable in M Dogan, in an energetic talk, described his theorem, which asserts the following. If C satisfies the free amalgamation property, and has two additional minor properties (all 1-element structures are isomorphic, and some pair of distinct points enter into some relation), then the embedding can be chosen to be rigid, which means that any automorphism of N extends uniquely to an automorphism of M.

This result should allow us to find many subgroups of the automorphism groups of such homogeneous structures; as above, Aut(N) is a subgroup of Aut(M).

The end of a very nice meeting; so we all rode off into the sunset, with thanks to the organisers SSS (Şule, Selda and Sibel). Although I was not at my best, I hope I was able to be of at least some help to some people!



About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s