## 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$.

Advertisements