BMC/BAMC 2015 Tuesday to Thursday: Mantel’s Theorem and the foundations of mathematics

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 n vertices containing no triangles is \lfloor n^2/4 \rfloor. Talbot indicated one of many nice proofs: for all vertices x and y such that \{x,y\} is an edge we have

(\delta(x) - 1) + (\delta(y) - 1) \le n-2.

So summing over all m edges we get

\sum_x \delta(x)^2 = \sum_{\{x,y\}} (\delta(x) + \delta(y)) \le nm.

The left-hand side is maximized when all the degrees are as equal as possible. So we can assume that \delta(x) \le \sqrt{m} for each vertex x. By the Handshaking Lemma we get 2m \le n\sqrt{m}. Hence 4m^2 \le n^2m and m \le n^2/4. Moreover, it follows that there is a unique extremal graph, namely the complete bipartite graph with parts of sizes \lfloor n/2 \rfloor and \lceil n/2 \rceil.

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 3-uniform hypergraph free of the tetrahedron \{ \{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\} \} is 5/9. Turan gave an explicit construction attaining this bound: Let X = \{1,\ldots, r\}, Y = \{r+1,\ldots, 2r\} and Z = \{2r+1, \ldots, 3r\} and let the 3-edges be all 3-subsets of \{1,\ldots, 3r\} of the form \{x,y,z\}, \{x,x',y\}, \{y,y',z\} or \{z,z',x\}. Given any 4 vertices there must be two in the same subset, say X, and a tetrahedron is then ruled out because the graph has no edges of the form \{x,x',z\}. The number of edges is roughly r^3 + 3r^2/2 \times r = 5r^3/2 so the asymptotic density is 5/2 \left/\right. 27/6 = 5/9.

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 \kappa such that \kappa is the union of fewer than \kappa cardinals each smaller than \kappa) 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 G on a set of cardinality \kappa is universal for a set of graphs \mathcal{G} if every graph in \mathcal{G} is isomorphic to an induced subgraph of G.

Theorem. Let \kappa be a singular cardinal of countable cofinality. There is no graph G of cardinality \kappa containing no clique of cardinality \kappa, and universal for graphs of cardinality \le \kappa containing no clique of cardinality \kappa.

Proof. Suppose G is such a graph. Let \kappa = \cup_{i < \omega} \lambda_i where \lambda_i < \kappa for each i. Make a new graph G^+ by taking disjoint cliques H_i of cardinality \lambda_i for each i < \omega, and joining all vertices in G to all vertices in each H_i. Note that G^+ has no clique of cardinality \kappa. Let f : G^+ \rightarrow G be an injection. If x \in H_i and y \in H_j where i < j then \{x, f^{j-i}(y)\} is an edge of G^+, and hence \{f^{i+1}(x), f^{j+1}(y) \} is an edge of G. It easily follows that

\cup_{i < \omega} f^{i+1}(H_i)

is a clique in G of cardinality \cup_{i < \omega} \lambda_i = \kappa. \Box

In fact this proof even shows that no such G 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 \kappa there exist a graph of cardinality \kappa universal for all graphs of cardinality \le \kappa.


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

%d bloggers like this: