## Local Events, Turan’s Problem and Limits of Graphs and Hypergraphs

I will write a little about how hectic things are now here at HU, and make two (somewhat related) follow-ups on previous posts: Tell you about Turan’s problem, and about Balázs Szegedi’s lecture from Marburg dealing with limits of graphs and hypergraphs.

## Local Events

The second semester at HU started on Sunday, May 11th and it will run until August. This is due to the 3-months Israeli Professors’ strike at the beginning of the academic year. Issues regarding the strike and Israeli academics are quite interesting and we may come back to them. Let me make just one little remark: There is an initiative to transform Israeli universities to a more “market-based” structure. US universities and the new evaluation system in the UK are mentioned as examples, and the Australian academic reforms are often regarded as an act to follow. I was always quite negative about this initiative and skeptical even about the Australian example, and the following post by Terry Tao is telling regarding the Australian reforms. (See also the new blog mathematics in Australia.)

Thia semester I am teaching the basic course in combinatorics and a seminar in probabilistic combinatorics. As usual, things are hectic here. Our yearly spring school “Midrasha Matematicae” is devoted this year to Cluster algebras, quantization and higher Teichmuller theory. Cluster algebras were invented by Sergey Fomin and Andrei Zelevinski (both are visiting) and the starting points were questions in combinatorial representation theory and total positivity. In combinatorics they led, among many other things, to nice results regarding “Somos sequences” and to new extensions of the associahedron (=Stasheff polytopes). There is a lot of activity regarding cluster algebra related to geometry, algebra, categorization, tropicalization, and other high flight mathematics.

Beside that, we have our usual Monday’s combinatorics seminar, (yesterday – Doron Zeilberger), and Wednesday’s CS theory seminar, and Thursday’s quantum computing seminar (with some extra lectures this week by Daniel Gottesman), and the colloquium, and the “basic notions” seminar, (and the Amitsur algebra seminar, and PDE seminar,) and Tuesday’s Dynamics and probability seminar, and Sunday’s game theory seminar, and the “Rationality on Friday” seminar (and a few more).  The first week also started with Avi Wigderson giving a great popular lecture on the “digital envelope” and its uses. He gave a lovely colorful (literally) explanation for zero-knowledge proofs.

Aner’s colloquium on the Ore Conjecture was a wonderful mixture of various issues. The proof (what was “left” to be proved after earlier works was proving the conjecture for finite simple groups of Lie type over fields of less than eight elements), relied on deep representation theory (detailed understanding of Deligne-Lusztig characterization of representations of these groups), complicated inductive procedures, and three years of CPU time based on complicated computational group theory to give the necessary basis for the other methods. (Of course, it relies on the classification theorem for finite simple group.) … I am not sure if I will continue with real-time blogging like this. (Little update (May 22): I forgot to mention talks by two fresh Wolf prize laureates; a beautiful and clear talk by Griffiths on the Hodge conjecture yesterday; Deligne will speak next week.)

## Turan’s  problem

In the post regarding extremal combinatorics I left it to the readers to guess a conjecture on collections of triangles without a “tetrahedron”; Let’s do it together. Then I will give a few more details about a lecture by Szegedy from the Marburg conference , on graphs and hypergraphs limits. These two topics are not entirely unrelated.

Let’s try to think together what can be an example of a 3-uniform hypergraph (collection of triples) on n vertices N={1,2,3,…,n} without a “tetrahedron” – {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d},  with as many triangles as possible:

Step 1: So to start we can divide our vertices to 3 as equal as possible parts A, B and C, and take all triangles {a,b,c}. This gives roughly 2/9 of all triangles. It does not contain even three triangles of a tetrahedron: we can do better. (To find the maximum number of triangles without having three triangles spanned on four vertices ia also a very nice problem.)

Step 2: OK, let’s divide N to two equal as possible parts A and B, and take all triangles of the form a a’ b and a b b’  — We got many triangles but this construction is not good, we have a tetrahedron a a’ b b’. We can keep this example to another problem.

Step 3: OK, divide N into equal parts A and B and take only triangles of the form {a,a’,b}. This gives … 3/8 of all triangles, an improvement.

Step 4: Hmm, we can now optimize the sizes of A and B. If we take A to contain 2/3 of the vertices, we get roughly 4/9 of all triangle.

Step 5: We can apply the “symmetry-breaking” of step 3 to the original construction of step 1. We can divide our vertices to three as equal as possible parts A, B and C and take all triangles {a,b,c} {a, a, ‘b}, {b,b’c}, and {c,c’a}.  This is Turan’s example. Turan conjectured in 1940 that this is the best example “on the nose” and his conjecture is still open.

When asking students to come up with examples of 3-uniform hypergraphs without tetrahedra, they often start with Step 1 and sometimes move directly to the right (conjectural) answer, and sometimes go through examples like the one in step 3 or try to partition the ground set into four parts.

I do not know how Turan reached his conjecture. Turan’s theorem and Turan’s problem, as well as the some basic problems regarding crossing numbers of complete bipartite graphs and complete graphs, were discovered when Turan was in a labor camp during World War II. He could not use pen and paper, so doing combinatorics was easier than working on analytic number theory which was his main area of research. Vera Sos (who is visiting here) referred me to Turan’s welcome note in the Journal of Graph Theory (J. Graph Theory 1(1977) 7-9), which includes some memories of his graph theory research in the labor camps.  It starts with: “It sounds a bit incredible but it is true,” and it is quite incredible indeed!

An amazing fact is that there are many examples by Brown and by Kostochka which give precisely the same number of triangles as Turan’s original example.

I will be happy to further discuss Turan’s problem. Here is one small observation.

Can there be an even simpler theorem about triangle-free graphs than Turan’s theorem?

When we move to the complement graph, Turan’s theorem tells us that the minimum number of edges in a graph without an independent set of three points is obtained by the union of two complete graphs of equal as possible sizes. Here is something even simpler:

A graph with no three independent vertices has at most two connected components.

This very simple fact does generalize to:

A three uniform hypergraph H on n vertices so that every four vertices span a triangle satisfies: $\dim H_1(H',k) \le n-2$ .

Here $H_1(H',k)$ is the first homology group over an arbitrary field of coefficients $k$, and H’ is the simplicial complex on N with a complete graph as the 1-dimensional skeleton, whose 2-faces are the set of our triangles.

I do not know a “conceptual” proof for this fact. (Such a proof may lead to extensions toward Turan’s problem.)  Homology inclined readers are welcomed to try.

## Limits of graphs and hypergraphs

Let me mention one talk from Marburg. When do we say that a sequence of graphs $G_n$ (or of hypergraphs) has a limit? First we need the important notion of graph homomorphisms.

A map between the vertices V(G) of a graph G and the vertices V(H) of a graph H is a homomorphism, if it maps every edge to an edge. (Ashkara an edge; mapping two adjacent vertices to the same vertex is forbidden.)

Studying graph homomorphisms leads to a lot of very nice combinatorics and is related to logic, algebraic topology, and probability. Let Hom(G,H) be the set of homomorphisms from G to H and let t(G,H) be the probability that a random function from V(H) to V(G) is an homomorphism.

We say that a sequence of graphs $(G_n)$ tends to a limit if for every fixed graph F the series $t(F,G_n)$  is convergent. (This concept is related to quasirandomness of graphs, to Szemeredi’s regularity lemma and its recent extensions, to property testing, and to various other notions.)  The limit objects for graphs are measurable symmetric functions from $I^2$ into $I$ ($I$ =[0,1]) and they are called “graphons”. (The definition of converging sequences for hypergraphs is similar but the limit objects are more complicated.)

I did not find Balasz’ nice lecture online but here is a previous lecture by Lovasz. Lovasz and Sos proved that every “step function” is “finitely forcible”. (I will not explain these terms here.) The new development is that the conjecture that every “finitely forcible” graphon is a “step function” was disproved and this makes the theory even richer and more interesting.

We can ask a question related to both topics.

Problem: Consider all of Kostochka’s examples for Turan’s problem. (Those include Turan’s example as well as Brown’s.) Do they have a unique limit point?

Related posts: “Extremal Combinatorics I,” and over Terry Tao’s blog: (Luca Trevisan) Checking the Quasirandomness of Graphs and Hypergraphs

Arabic words which are part of Hebrew slang: ashkara – for real; sababa - cool, wonderful; walla – true;  ahla –  great; yalla - hurry up, c’mon, let’s go.