Source-linked AI summary
Hypergraphs do jump
Rahil Baber, John Talbot
TL;DR
For r-graphs, the location of jumps beyond the classical range remained unclear despite the failure of Erdős’s conjecture that every value below 1 is a jump. Using Razborov’s flag-algebra method, the authors establish jump intervals for 3-graphs, including the first examples beyond r!/r^r.
Problem
For r ≥ 3, the location of jumps or non-jumps in [r!/r^r, 5r!/2r^r) was previously unknown, although the conjecture that every α below 1 is a jump had been disproved.
Source: §1 · p. 2Method
The paper applies Razborov’s flag-algebra method, using probabilities of induced flags to analyze Turán-density bounds.
Source: §2.1 · p. 4Results
For r = 3, every α in [0.2299, 0.2316) is a jump, and every α in [0.2871, 8/27) is also a jump.
Source: §1 · p. 2, §2.4 · p. 8Takeaways & Limitations
These are the first examples of jumps for any r ≥ 3 in [r!/r^r, 1).
Source: §1 · p. 2Whether 2/9 is a jump for r = 3 remains unresolved; a proof along the same lines appears to require a very precise approximation of a Turán density.
Source: §3 · p. 10
Abstract
from arXiv · showhide
We say that $\alpha\in [0,1)$ is a jump for an integer $r\geq 2$ if there exists $c(\alpha)>0$ such that for all $\epsilon >0 $ and all $t\geq 1$ any $r$-graph with $n\geq n_0(\alpha,\epsilon,t)$ vertices and density at least $\alpha+\epsilon$ contains a subgraph on $t$ vertices of density at least $\alpha+c$. The Erd\H os--Stone--Simonovits theorem implies that for $r=2$ every $\alpha\in [0,1)$ is a jump. Erd\H os showed that for all $r\geq 3$, every $\alpha\in [0,r!/r^r)$ is a jump. Moreover he made his famous "jumping constant conjecture" that for all $r\geq 3$, every $\alpha \in [0,1)$ is a jump. Frankl and R\"odl disproved this conjecture by giving a sequence of values of non-jumps for all $r\geq 3$. We use Razborov's flag algebra method to show that jumps exist for $r=3$ in the interval $[2/9,1)$. These are the first examples of jumps for any $r\geq 3$ in the interval $[r!/r^r,1)$. To be precise we show that for $r=3$ every $\alpha \in [0.2299,0.2316)$ is a jump. We also give an improved upper bound for the Tur\'an density of $K_4^-=\{123,124,134\}$: $\pi(K_4^-)\leq 0.2871$. This in turn implies that for $r=3$ every $\alpha \in [0.2871,8/27)$ is a jump.
1 Introduction
The introduction places the search for jumps beyond the classical range against the failure of Erdős’s jumping constant conjecture. It proposes a threshold-family approach and uses a Turán-density bound to establish an interval of jumps for 3-graphs.
1 Introduction
- For r ≥ 3, Erdős established jumps below r!/r^r, while Frankl and Rödl disproved the conjecture that every value below 1 is a jump.Before this work, the location of jumps or non-jumps in [r!/r^r, 5r!/2r^r) was unknown; the authors present the first examples above r!/r^r.Source: §1 · pp. 1–2
- Erdős’s proposed route through F∗ fails because 2/9 is not its threshold, but a larger family F′ with minimum Lagrangian above 2/9 could still establish the jump.Theorem 1.2 connects being a jump with being a threshold for a finite family of r-graphs.Source: §1 · pp. 2–3
- Eight-vertex 3-graphs avoiding F′ still have Lagrangians above 2/9, and numerical evidence suggests c(2/9) would be at most 0.00009254 if 2/9 is a jump.Blow-ups of such graphs imply π(F′) > 2/9.Source: §1 · p. 3
- 0.2299 < min_{F∈F′} λ(F) = λ(F2) = 0.2316, yielding Theorem 1.1 by Lemma 1.3 and Theorem 1.2.The proposed family is F′ = {F1, F2, F3, F4, F5}.Source: §1 · p. 3
- Razborov’s flag-algebra method supplies the technique used to prove the required Turán-density bound.The authors describe it as improving the ability to compute and approximate Turán densities.Source: §1 · p. 3
2 Computing Tur´an densities via flag algebras
Razborov’s flag algebra method uses overlapping small subgraphs to sharpen Turán-density bounds through semidefinite programming. The paper illustrates the method and applies it to establish new upper bounds and jump intervals for 3-graphs.
2.1 Razborov’s method
- The flag algebra bound uses information from overlapping subgraphs, with positive semidefinite matrices yielding inequalities that can improve the basic averaging bound.Flags are r-graphs with labelled vertices; products of flag probabilities correspond to overlapping samples, whose sampling difference is negligible for large graphs.Source: §2.1 · pp. 4–5
2.2 An example
- For K4^-, the example takes l = 4 and uses three K4^--free 3-graphs and two admissible flags to recover the bound π(K4^-) ≤ 1/3.The example computes coefficients from probabilities of pairs of induced flags in each 4-vertex graph, then formulates the optimization as a semidefinite program.Source: §2.2 · pp. 6–7
2.3 Proof of Lemma 1.3
- 0.2299 is an upper bound for π(F′), certified with rational positive semidefinite matrices that can be checked using integer operations.The computation uses 4042 admissible 7-vertex 3-graphs and six choices of types; the authors selected the types experimentally because using all types of size at most 5 would be computationally intractable.Source: §2.3 · pp. 7–8
2.4 Other results
- 0.2871 is a new upper bound for π(K4^-), improving the reproduced 0.2978 bound.The calculation uses l = 7 and four types, with positive semidefinite matrices found by solving a semidefinite program.Source: §2.4 · p. 8
- α ∈ [0.2871, 8/27) is a jump interval for r = 3.The paper states that this second new interval follows from Theorem 2.2.Source: §2.4 · p. 8
2.5 Solving the semidefinite program
- A change of basis separates flag-space components into two blocks, making the semidefinite program block diagonal and potentially reducing computation.The construction uses the automorphism group of each type to build the basis.Source: §2.5 · pp. 9–10
3 Open problems
For r=3, the paper establishes [0.2299, 0.2316) as an interval of jumps but cannot resolve whether 2/9 is a jump. The authors identify obstacles to resolving that question and possible ways to improve Turán-density bounds.
3 Open problems
- [0.2299, 0.2316) is an interval of jumps for r = 3, but the authors' approach cannot resolve whether 2/9 is a jump.They state that π(F′) > 2/9.Source: §3 · p. 10
- Resolving whether 2/9 is a jump appears difficult: a proof by this approach would require a very precise Turán-density approximation, while the available non-jump technique fails there.The authors say that if 2/9 is a jump, its size is very small; the Frankl–Rödl method also fails at r!/r^r for every r ≥ 3.Source: §3 · p. 10
- The 0.2871 bound may be improved using larger flags or different order-5 types; larger flags may also improve bounds for the central Turán-density problem.The authors present these as likely or probable avenues for improvement.Source: §3 · p. 10