21 July 2005 in Combinatorics, Probability and Computing
A Fano configuration is the hypergraph of 7 vertices and 7 triplets defined by the points and lines of the finite projective plane of order 2. Proving a conjecture of T. Sós, the largest triple system on $n$ vertices containing no Fano configuration is determined (for $n> n_1$). It is 2-chromatic with $\binom{n}{3}-\binom{\lfloor n/2 \rfloor}{3} -\binom{\lceil n/2 \rceil}{3}$ triples. This is one of the very few nontrivial exact results for hypergraph extremal problems.
1 July 2005 in Combinatorics, Probability and Computing
Let ${\cal H}$ be a 3-uniform hypergraph on an $n$-element vertex set $V$. The neighbourhood of $a,b\in V$ is $N(ab):= \{x: abx\in E({\cal H})\} $. Such a 3-graph has independent neighbourhoods if no $N(ab)$ contains an edge of ${\cal H}$. This is equivalent to ${\cal H}$ not containing a copy of $\mathbb{F} :=\{ abx$, $aby$, $abz$, $xyz\}$. In this paper we prove an analogue of the Andrásfai–Erdös–Sós theorem for triangle-free graphs with minimum degree exceeding $2n/5$. It is shown that any $\mathbb{F}$-free 3-graph with minimum degree exceeding $(\frac{4}{9}-\frac{1}{125})\binom{n}{2}$ is bipartite, (for $n> n_0$), i.e., the vertices of ${\cal H}$ can be split into two parts so that every triple meets both parts. This is, in fact, a Turán-type result. It solves a problem of Erdös and T.Sós, and answers a question of Mubayi and Rödl that \[\ex(n,\mathbb{F}_{3,2})=\max\limits_{\alpha}(n-\alpha)\left({\alpha\atop2}\right)\]. Here the right-hand side is $\frac{4}{9}\binom{n}{3}+O(n^2)$. Moreover $e({\cal H})={\rm ex}(n,\mathbb{F})$ is possible only if $V({\cal H})$ can be partitioned into two sets $A$ and $B$ so that each triple of ${\cal H}$ intersects $A$ in exactly two vertices and $B$ in one.
1 January 2002 in Combinatorica
30 November 2008 in Journal of Combinatorial Theory, Series A
1 September 2009 in Combinatorics, Probability and Computing
It is shown that the size of a subgraph of Qn without a cycle of length 14 is of order o(|E(Qn)|).
18 October 2005 in Journal of Combinatorial Theory, Series A