Math-1538 · mathematics · Combinatorics

Math-1538

Expansion can hide only global Sidorenko obstructions

Status Partially solved · unsolvedmath.comLLM status Open unverified

Top Open Problems Not reported cataloguedPartially solvedOpen

Statement

Definitions and mathematical statement

A finite $k$-uniform hypergraph $H$ has a vertex set $V(H)$ and an edge set consisting of $k$-element subsets of $V(H)$. For another such hypergraph $G$ with $N\ge1$ vertices, let $\operatorname{hom}(H,G)$ count all maps $f:V(H)\to V(G)$ taking each edge of $H$ to an edge of $G$. Maps need not be globally injective, but must be injective on each edge. Put \[ t(H,G)=\frac{\operatorname{hom}(H,G)}{N^{|V(H)|}},\qquad p(G)=\frac{k!|E(G)|}{N^k}. \] Call $H$ Sidorenko if $t(H,G)\ge p(G)^{|E(H)|}$ for every finite $k$-uniform $G$. A non-Sidorenko hypergraph has a host $G$ violating this inequality. These are homomorphism densities, so vertices belonging to different edges are allowed to acquire the same image.

For an integer $r>k$, form the $r$-expansion $H^{(r)}$ by choosing, for every edge $e$ of $H$, a new set $W_e$ of $r-k$ vertices and replacing $e$ by $e\cup W_e$. All $W_e$ are mutually disjoint and disjoint from $V(H)$; each new vertex belongs to exactly one edge. The question is whether there exist $k\ge2$, $r>k$, and a finite non-Sidorenko $k$-uniform hypergraph $H$ such that $H^{(r)}$ is Sidorenko. For the expanded hypergraph the defining inequality uses $r$-uniform hosts and their corresponding density $r!|E(G)|/N^r$.

Short English statement

Can adding private vertices to every hyperedge turn a non-Sidorenko hypergraph into a Sidorenko hypergraph?

Sources

  • S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20000886 (AIM-COMBINATORICS-0011), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
  • S2 American Institute of Mathematics, High-dimensional phenomena in discrete analysis, item 3.2. Original workshop question underlying AIM-COMBINATORICS-0011. http://aimpl.org/highdimdiscrete/3/.

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 0

No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.