Loading Web-Font TeX/Main/Regular
| 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. Add remark

      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.

                  Add remark

                  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.

                      Add remark

                      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.