| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

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.
    1. 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). $$
        1. 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$.

                  Conjecture 4.2.

                  [Frankl-Rödl (see [erdos+nesetril+rodl:90]]{Matchings] $$ |M| = o(n^2). $$
                      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.