Grid-free linear hypergraphs via Cayley-Bacharach

1. Problem Statement and Context

The Core Problem:
The paper addresses a fundamental question in extremal hypergraph theory: What is the maximum number of edges, denoted $\text{ex}_{\text{lin}}(n, G_{r \times r})$, in an $r$-uniform linear hypergraph on $n$ vertices that contains no copy of the $r \times r$ grid ($G_{r \times r}$)?

• Definitions:
  • An $r$-uniform linear hypergraph is a hypergraph where every edge contains exactly $r$ vertices, and any two distinct edges intersect in at most one vertex.
  • The $r \times r$ grid ($G_{r \times r}$) consists of $r^2$ vertices arranged in a grid, with $2r$ edges: $r$ "row" edges and $r$ "column" edges.
• Theoretical Bounds:
  • Linearity imposes a universal upper bound of $|E| \le \binom{n}{2} / \binom{r}{2} \approx \frac{n^2}{r(r-1)}$. Equality holds for Steiner systems $S(2, r, n)$.
  • The goal is to construct dense (quadratic in $n$) linear hypergraphs that avoid $G_{r \times r}$.
• State of the Art (Pre-Paper):
  • For $r \ge 4$, F"uredi and Ruszink'o (and later others) constructed near-Steiner systems with $\Theta(n^2)$ edges avoiding the grid.
  • For $r = 3$, these methods failed to produce quadratic constructions. Previous best lower bounds were sub-quadratic ($\Omega(n^{1.8})$). Recent breakthroughs by Gishboliner–Shapira and Solymosi established $\Theta(n^2)$ for $r=3$ using specific algebraic constructions (quadratic residues and conics), but these were specific to $r=3$.
• The Gap: There was no unified construction proving $\text{ex}_{\text{lin}}(n, G_{r \times r}) = \Theta_r(n^2)$ for all $r \ge 3$.

2. Methodology: The Cayley-Bacharach Connection

The paper's primary innovation is leveraging the Cayley-Bacharach theorem from algebraic geometry to enforce grid-freeness.

• The Geometric Setup:
  The author constructs hypergraphs using points and lines in the affine plane $AG(2, q)$ over a finite field $\mathbb{F}_q$.

  • Vertices: A union of a set of horizontal lines ($A$) and a conic section (specifically a parabola $B = \{(x, x^2)\}$).
  • Edges: Defined by non-horizontal affine lines $\ell$. An edge $e(\ell)$ consists of the intersection of $\ell$ with the horizontal lines ($r-1$ points) plus exactly one point chosen from the intersection $\ell \cap B$.

• The Cayley-Bacharach Mechanism:
  The proof of grid-freeness relies on Lemma 3.1 (Cayley-Bacharach Theorem):

  If two plane curves $D_1, D_2$ of degree $r$ intersect in $r^2$ distinct points, then any curve of degree $\le 2r-3$ passing through $r^2-1$ of these points must pass through the $r^2$-th point as well.

  The Logic of the Proof:

  1. Assume a grid $G_{r \times r}$ exists in the constructed hypergraph.
  2. The $r$ rows and $r$ columns correspond to $r$ lines each, forming two degree-$r$ curves $D_1$ and $D_2$. Their intersection $X$ contains the $r^2$ grid vertices.
  3. The construction ensures that all vertices lie on a specific algebraic curve $C_0$ (the union of the horizontal lines and the parabola).
  4. The degree of $C_0$ is calculated to be $r+1$ (or $2r-3$ in the specific construction for Theorem 1.1).
  5. If a grid existed, one could construct a curve of degree $\le 2r-3$ that passes through all grid vertices except one (specifically the one on the parabola that was "missed" by the edge definition).
  6. By Cayley-Bacharach, such a curve must pass through the last point. This creates a contradiction because the construction explicitly prevents the edge from containing that specific point.

3. Key Contributions and Results

The paper provides two main theorems establishing the existence of dense, grid-free linear hypergraphs for all $r \ge 3$.

Theorem 1.1: Unified Quadratic Construction

• Result: For every $r \ge 3$ and sufficiently large odd prime power $q$, there exists an $r$-uniform linear hypergraph $H_{r,q}$ with:
  • Vertices: $|V| = rq$
  • Edges: $|E| = \frac{q^2 + 2q - 1}{2} \approx \frac{1}{2r^2} n^2$
  • Property: Contains no copy of $G_{r \times r}$.
• Significance: This is the first construction proving $\text{ex}_{\text{lin}}(n, G_{r \times r}) = \Theta_r(n^2)$ for all $r \ge 3$, unifying the previously disparate cases of $r=3$ and $r \ge 4$.
• Note: While the constant $\frac{1}{2r^2}$ is smaller than the near-Steiner bounds for $r \ge 4$ (which are closer to $\frac{1}{r(r-1)}$), the primary contribution is the existence of a quadratic bound for $r=3$ via a unified method.

Theorem 1.2: Avoiding Punctured Intersections

• Result: The author defines "punctured intersections" ($P_{r,t}$), which are grid-like structures where $t$ row-column intersections are removed and replaced by private filler vertices to maintain uniformity.
• Construction: A denser model $H^{\parallel}_{r,q}$ is constructed using $r$ parallel lines.
• Property: This hypergraph avoids all $P_{r,t}$ for $t \le r-2$.
• Significance: This demonstrates the robustness of the Cayley-Bacharach approach. It shows that the method doesn't just forbid the full grid but forbids a whole family of "almost grid" configurations, provided the number of missing points ($t$) is small enough relative to the degree constraints.

4. Technical Details of the Construction

The paper details two specific constructions:

1. The Parabola Construction (Theorem 1.1):

   • Vertices: $A = \bigcup_{t=1}^{r-1} \{(x, \alpha_t) : x \in \mathbb{F}_q\}$ (horizontal lines) and $B = \{(x, x^2) : x \in \mathbb{F}_q\}$ (parabola).
   • Edges: For every non-horizontal line $\ell$, the edge is $(\ell \cap A) \cup \{p(\ell)\}$, where $p(\ell)$ is a single point from $\ell \cap B$.
   • Why it works: The parabola $B$ intersects any line in at most 2 points. The specific selection rule ensures that if a grid were formed, the "missing" point would violate the degree constraints of the Cayley-Bacharach theorem.

2. The Parallel Lines Construction (Theorem 1.2):

   • Vertices: $r$ parallel lines $L_1, \dots, L_r$.
   • Edges: Intersections of all non-parallel lines with the set of vertices.
   • Why it works: This is a simpler geometric setup where the "ambient curve" is just the union of the $r$ parallel lines (degree $r$). The degree budget lemma (Lemma 4.3) shows that one cannot form a punctured grid with $t \le r-2$ holes without violating the intersection properties of the underlying algebraic curves.

5. Significance and Future Directions

• Unification: The paper resolves the $r=3$ case using the same geometric machinery that works for $r \ge 4$, replacing ad-hoc algebraic identities (like those used in previous $r=3$ proofs) with a general geometric principle.
• Generalization to Higher Dimensions: The author extends the Cayley-Bacharach principle to higher dimensions (Theorem 5.1), connecting it to the Combinatorial Nullstellensatz and the Erdős Box Problem.
  • The paper suggests that many Turán-type lower bounds in extremal combinatorics might be manifestations of this "Cayley-Bacharach completion obstruction."
  • Specifically, it links the construction of $K^{(r)}_{2,\dots,2}$-free hypergraphs to the inability of low-degree polynomials to separate a single point from a complete intersection.
• Limitations: The current constructions do not yet reach the optimal edge density of $\frac{n^2}{r(r-1)}$ (Steiner systems) for $r \ge 4$, though they achieve the correct asymptotic order $\Theta(n^2)$.

Conclusion

Cosmin Pohoata's paper provides a powerful new tool for extremal hypergraph theory. By translating the problem of avoiding grid configurations into a problem of algebraic curve intersections, the author utilizes the Cayley-Bacharach theorem to prove the existence of dense, grid-free linear hypergraphs for all uniformities $r \ge 3$. This approach not only solves a specific open problem for $r=3$ but also offers a unified framework for understanding and constructing hypergraphs that avoid various local configurations.