On Tuesday, John Talbot gave a great short talk on Mantel’s Theorem: analogues and extensions. Mantel’s Theorem states that the maximum number of edges in a graph on vertices containing no triangles is . Talbot indicated one of many nice proofs: for all vertices and such that is an edge we have
So summing over all edges we get
The left-hand side is maximized when all the degrees are as equal as possible. So we can assume that for each vertex . By the Handshaking Lemma we get . Hence and . Moreover, it follows that there is a unique extremal graph, namely the complete bipartite graph with parts of sizes and .
Talbot mentioned a number of other analogous problems for other forbidden subgraphs, and extensions where graphs are generalized to uniform hypergraphs. He ended with some open questions. The most interesting for me was a conjecture of Turan, that the asymptotic density of edges in a -uniform hypergraph free of the tetrahedron is . Turan gave an explicit construction attaining this bound: Let , and and let the -edges be all -subsets of of the form , , or . Given any vertices there must be two in the same subset, say , and a tetrahedron is then ruled out because the graph has no edges of the form . The number of edges is roughly so the asymptotic density is .
On Thursday there was another great talk by Mirna Džamonja on Current challenges in foundations of mathematics, logic and set theory. Most of the talk was a fascinating tour through the history of foundations, from Hilbert’s programme to Gödel, and then post-Gödel results such as the independence of the continuum hypothesis from ZFC (giving a surprising answer to Hilbert’s Problem 1) and a brief mention of Voevodsky’s univalent foundations, which seems to have connections to the proof assistant Coq mentioned in Monday’s panel discussion.
She ended with some results on random graphs that suggests that singular cardinals (i.e. cardinals such that is the union of fewer than cardinals each smaller than ) have some special ‘rigidity’ properties, in contrast to the free-for-all often permitted by ZFC. Her final result is elegant and even has a simple proof in ZF. To state it we need the following definition: a graph on a set of cardinality is universal for a set of graphs if every graph in is isomorphic to an induced subgraph of .
Theorem. Let be a singular cardinal of countable cofinality. There is no graph of cardinality containing no clique of cardinality , and universal for graphs of cardinality containing no clique of cardinality .
Proof. Suppose is such a graph. Let where for each . Make a new graph by taking disjoint cliques of cardinality for each , and joining all vertices in to all vertices in each . Note that has no clique of cardinality . Let be an injection. If and where then is an edge of , and hence is an edge of . It easily follows that
is a clique in of cardinality .
In fact this proof even shows that no such exists if we omit the word 'induced' in the definition of universal. In contrast the incredible countable random graph contains every finite or countable graph as an induced subgraph, and it is known that under GCH for every cardinal there exist a graph of cardinality universal for all graphs of cardinality .