4. Ruzsa-Szemerédi Theorem and Relatives
Let the $3$-graph $C_5^-$ be obtained from $C_5^3$ by removing one edge. An example of a $C_5^-$-free $3$-graph can be obtained by taking a complete $3$-partite $3$-graph and repeating this construction recursively within each of the three parts. This gives density $1/4$ in the limit.-
Conjecture 4.1.
[Erd\H os, Frankl, and R\] For any $r\ge 3$ and $s\ge 4$ we have $$ f^r(n,s(r-2)+3,s)=o(n^2). $$-
Remark. In [sarkozy+selkow:05] it is proved that $f^r(n,s(r-2)+[{\log_2s}],s)=o(n^2)$. The first remaining open case is to prove the conjecture for $f^3(n,7,4)$ (probably very hard).
-
Remark. One possible direction here is to look at multiple hypergraphs (when the same $r$-tuple can appear a multiple number of times) and ask for $F^r(n,p,s)$ maximum size of an $r$-multi-hypergraph such that every $s$-set spans at most $p$ edges. See Füredi and Kündgen [furedi+kundgen:02] for results in the graph case ($r=2$).
-
-
A related question is as follows. Let $A$, $B$, and $C$ be disjoint sets each of size $n$. Let $M_1,\dots ,M_l$, be matchings, where each edge of $M_i$ has one point in each of $A$, $B$, and $C$. The forbidden configuration is: three edges $abc$, $a'b'c'$, $a''b''c''$ all in some $M_i$ and one edge of the form $ab'c''$ in some other $M_j$ (that is, the edge from $M_j$ crosses the three edges of $M_i$). Additionally, we require that the union of all matchings $M_i$ makes a simple (linear) $3$-graph, call it $M$.If true, this implies Roth’s Theorem (every set of integers of positive upper density has a $3$-term arithmetic progression). An obvious generalization is to consider the $k$-graph version where we have parts $A_1, ..., A_k$, each of size $n$, and instead of three edges in $M_i$ we take $k$ edges in $M_i$ and another crossing edge as the forbidden configuration; as before, we require that the union $M$ is a linear $k$-graph. Again, we believe that $|M| = o(n^2)$ and, if true, this would imply Szemerédi’s Theorem. The case $k=2$ is equivalent to the Ruzsa–Szemerédi Theorem that $f^3(n,6,3)=o(n^2)$.
-
The following conjecture seems to be related.
Conjecture 4.3.
[Solymosi, Oberwolfach 2011] Let $F$ be a graph and $\alpha>1$ be such that $\operatorname{ex}(n,F)=\Omega(n^{\alpha}$). Then for any $\epsilon > 0$ there is $n_0$ so that if $n > n_0$ and a graph $H$ is the edge-disjoint union of $m=\lceil \epsilon n^{\alpha}\rceil$ copies of $F$, then $H$ contains another copy of $F$ (i.e. has at least $m+1$ copies of $F$).
Cite this as: AimPL: Hypergraph Turán problem, available at http://aimpl.org/hypergraphturan.