Loading Web-Font TeX/Math/Italic
| Register
\newcommand{\Cat}{{\rm Cat}} \newcommand{\A}{\mathcal A} \newcommand{\freestar}{ \framebox[7pt]{$\star$} }

3. Extremal graph theory

    1. How badly can Sidorenko fail for hypergraphs


      Add remark

      Conjecture 3.1.

      [Jacob Fox] Let H be a 3-uniform, 3-partite hypergraph. Then any n-vertex 3-uniform hypergraph with pn^3 edges contains at least p^{Ce(H)}n^{V(H)} copies of H.
          If H\subset K_{t,t,t}^{(3)} with t=v(H)/3, then the number of copies of H is known to be at least p^{(v(H)/3)^3}n^{v(H)}.

      For graphs, the bound p^{e(H)+v(H)/2}n^{v(H)} is known. This might extend directly to hypergraphs.

        • Expansion of non-Sidorenko graphs

              Given a k-graph F, define the r-expansion of F to be the r-graph obtained by enlarging each k-edge of F with a set of r-k vertices of degree one.

          Add remark

          Problem 3.2.

          [Sam Spiro] Does there exist a non-Sidorenko (hyper)graph H whose r-expansion is Sidorenko?
              It is known that an expansion of a Sidorenko graph is Sidorenko.

          It is known that C_5 and its 3-expansion are not Sidorenko. More generally, if the girth (length of the shortest loose cycle) of a hypergraph F is odd, then F is not Sidorenko.

            • Induced packing and covering

                  Let H be a fixed graph, G an n-vertex graph. If the minimum number of edges needed to add or remove from G in order to remove all induced copies of H is o(n^2), then the regularity lemma implies that the maximum number of induced copies of H, with each pair intersecting in at most one vertex, is o(n^2).

              Add remark

              Problem 3.3.

              [Jacob Fox] Can we get better bounds, even for the case H=C_5?

                • Turan exponents of hypergraphs


                  Add remark

                  Conjecture 3.4.

                  [Jonathan Tidor] There exists c>0 such that the following holds. If H is an n-vertex, 3-uniform hypergraph with at least n^{3-c/d} edges, then H contains some/every 3-uniform, 3-partite linear hypergraph on d vertices with at least d^2/100 edges.
                      It is known that if H has \geq n^{3-c/d^2} edges, then it contains K_{d,d,d}^{(3)}.

                  Interesting cases are when H is the set of triangles in some graph G, or a p-random subset of triangles in G.

                      Cite this as: AimPL: High-dimensional phenomena in discrete analysis, available at http://aimpl.org/highdimdiscrete.