RECORD
Extremal numbers and Sidorenko's conjecture
Combinatorics · Submitted 10 Jul 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim With this application in mind, we find a range of new counterexamples to the conjecture for hypergraphs, including all linear hypergraphs containing a loose triangle and all $3$-partite $3$-uniform tight cycles.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Sidorenko's conjecture states that, for all bipartite graphs $H$, quasirandom graphs contain asymptotically the minimum number of copies of $H$ taken over all graphs with the same order and edge density. While still open for graphs, the analogous statement is known to be false for hypergraphs. We show that there is some advantage in this, in that if Sidorenko's conjecture does not hold for a particular $r$-partite $r$-uniform hypergraph $H$, then it is possible to improve the standard lower bound, coming from the probabilistic deletion method, for its extremal number $\mathrm{ex}(n,H)$, the maximum number of edges in an $n$-vertex $H$-free $r$-uniform hypergraph. With this application in mind, we find a range of new counterexamples to the conjecture for hypergraphs, including all linear hypergraphs containing a loose triangle and all $3$-partite $3$-uniform tight cycles.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Sidorenko's conjecture states that, for all bipartite graphs $H$, quasirandom graphs contain asymptotically the minimum number of copies of $H$ taken over all graphs with the same order and edge density. | background 1.00 | 0.03 | 0.03 | asserted 0.77 |
| s1 | While still open for graphs, the analogous statement is known to be false for hypergraphs. | background 0.96 | 0.04 | 0.03 | asserted 1.00 |
| s2 | We show that there is some advantage in this, in that if Sidorenko's conjecture does not hold for a particular $r$-partite $r$-uniform hypergraph $H$, then it is possible to improve the standard lower bound, coming from the probabilistic deletion method, for its extremal number $\mathrm{ex}(n,H)$, the maximum number of edges in an $n$-vertex $H$-free $r$-uniform hypergraph. | contribution 0.53 | 0.91 | 0.57 | asserted 0.64 |
| s3 | With this application in mind, we find a range of new counterexamples to the conjecture for hypergraphs, including all linear hypergraphs containing a loose triangle and all $3$-partite $3$-uniform tight cycles. | result 0.90 | 0.96 | 0.45 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Sidorenko's conjecture states that, for all bipartite graphs $H$, quasirandom graphs contain asymptotically the minimum number of copies of $H$ taken over all graphs with the same order and edge density. While still open for graphs, the analogous statement is known to be false for hypergraphs. We show that there is some advantage in this, in that if Sidorenko's conjecture does not hold for a particular $r$-partite $r$-uniform hypergraph $H$, then it is possible to improve the standard lower bound, coming from the probabilistic deletion method, for its extremal number $\mathrm{ex}(n,H)$, the maximum number of edges in an $n$-vertex $H$-free $r$-uniform hypergraph. With this application in mind, we find a range of new counterexamples to the conjecture for hypergraphs, including all linear hypergraphs containing a loose triangle and all $3$-partite $3$-uniform tight cycles.
Human review
How the literature uses it
3 arXiv papers cite this in 8 sentences
Papers citing it · 5 sentences without a confident label
Uses its method or tool 1 paper
-
Our proof of <Ref> is based off the proof of <Ref> from [ref] which relies on the tensor product trick.
Sidorenko Hypergraphs and Random Tur\'an Numbers · Proof of <Ref> and its Corollaries · 0.98
Cites it as background 1 paper
-
Finally, we recall that a graph with odd girth is not Sidorenko (see for instance [ref] ).
Uncommon linear systems of two equations · Introduction · 0.97
What it cites · 2 sentences without a confident label
Cites as background 6 papers
-
From an extremal viewpoint, these are some of the most closely studied hypergraphs (see, for example, [ref] ).
The Tur\'an density of tight cycles in three-uniform hypergraphs · Introduction · 0.99
-
The necessity of the bipartiteness condition is straightforward to verify, but its sufficiency remains wide open despite significant attention in recent years [ref] .
On the logarithimic calculus and Sidorenko's conjecture · Introduction · 0.95
-
The necessity of the bipartiteness condition is straightforward to verify, but its sufficiency remains wide open despite significant attention in recent years [ref] .
An information theoretic approach to Sidorenko's conjecture · Introduction · 0.95
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.