| 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.