On the Turán number of the G 3 × 3 G_{3\times 3} in linear hypergraphs
József Solymosi · 2025
Read On the Turán number of the G 3 × 3 G_{3\times 3} in linear hypergraphs by József Solymosi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16973.txt.
Introduction
József Solymosi improves a lower bound in extremal combinatorics with a single dense construction. His 2025 paper concerns 3-uniform linear hypergraphs, networks where each link joins three points and any two links share at most one point. The question is how dense such a network can be while holding no 3 by 3 grid pattern. Solymosi builds a grid-free family denser than any known before, which raises the floor on the Turán number for the grid.
Catalog record
| CREATOR | József Solymosi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 5 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-16973
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Turán number of the G 3 × 3 G_{3\times 3} in linear hypergraphs
József Solymosi
Abstract
. We show a construction for dense 3-uniform linear hypergraphs without 3 × 3 3\times 3 grids, improving the lower bound on its Turán number.
1.
Introduction
Finding the Turán number of hypergraphs is challenging. The typical question asks for the maximum number of edges that can be avoided in a given hypergraph.
There are a few examples only when sharp bounds are known. Such questions are even more challenging in an important subfamily called
linear hypergraphs
.
In an
r
-uniform linear hypergraph, every hyperedge has
r
vertices, and any pair of edges have at most one common vertex.
An
r
-uniform linear hypergraph on
r^{2}
vertices is called an
r
by
r
grid if it is isomorphic to a pattern of
r
horizontal and
r
vertical lines.
Answering a question by Füredi and Ruszinkó
[
2
]
about hypergraphs avoiding
3\times 3
grids (denoted by
G_{3\times 3}
), Gishboliner and Shapira gave a construction for dense linear 3-uniform hypergraphs not containing
G_{3\times 3}
.
Figure 1
.
A
G_{3\times 3}
hypergraph on nine vertices with six edges
Extremal problems about
G_{3\times 3}
are important due to the connection to the Brown-Erdős-Sós conjecture, coding theory and geometric application (see examples in
[
2
]
[
1
]
and
[
3
]
).
Theorem 1.1
(Gishboliner and Shapira
[
1
]
)
.
For infinitely many
n
, there exists a linear
G_{3\times 3}
-free 3-uniform hypergraph with
n
vertices
and
(\frac{1}{16}-o(1))n^{2}
edges.
Füredi and Ruszinkó conjectured that there are arbitrarily large Steiner triple systems avoiding
r\times r
grids for any
r\geq 3
. We are unsure about this conjecture (particularly the
r=3
case), but at least we improve the Gishboliner-Sharipa bound.
2.
The new bound
As in many extremal constructions, we are using objects in finite geometries.
Theorem 1
.
For infinitely many
n
, there exists a linear
G_{3\times 3}
-free 3-uniform hypergraph with
n
vertices
and
\left(\frac{1}{12}-o(1)\right)n^{2}
edges.
Proof.
First, we reprove the Gishboliner-Shapira bound with the constant
\frac{1}{16}
in a different way.
Let
q
be a prime power, let
\mathbb{F}_{q}
be the finite field of order
q
, and let
AG(2,q)
denote the Desarguesian affine plane of order
q
.
The vertex set of the hypergraph
\mathcal{H}
consists of the points of two parabolas,
V_{1}=\{(x,x^{2}):x\in\mathbb{F}_{q}\}
and
V_{2}=\{(x,x^{2}+1):x\in\mathbb{F}_{q}\}
.
The edge set is defined by collinear triples on the lines of the secants of
V_{1}
that have a non-empty intersection with
V_{2}
. If the line has two intersection points in
V_{2}
, choose only one of them to form an edge. Let’s count the number of edges.
There are
q
points in
V_{1}
, so the number of its secants is
\binom{q}{2}
. For two distinct points
(a,a^{2})
and
(b,b^{2})
the equation of the line connecting them is
y=(a+b)x-ab.
It intersects
V_{2}
iff the discriminant
(a-b)^{2}-4
is a quadratic residue or zero (we assumed here that
q
is odd, although one could perform similar calculations for even
q
as well). It is quadratic residue or zero for
q(q-\chi(-1))/2
ordered
(a,b)
,
a\neq b
pairs, where
\chi
is the quadratic character of
-1
in
\mathbb{F}_{q}
.
The number of intersecting secants, and therefore the number of edges is
E(\mathcal{H})=\frac{q(q-\chi(-1))}{4}\approx\frac{q^{2}}{4}=\left(\frac{|V(\mathcal{H}|}{2}\right)^{2}\frac{1}{4}=\frac{1}{16}|V(\mathcal{H}|^{2}
for large
q
.
This 3-uniform linear hypergraph doesn’t contain
3\times 3
grids. If there were one in
\mathcal{H}
, then six of its vertices were in
V_{1}
, so by Pappus’ theorem
*
*
*
Pappus’ theorem holds over finite fields (or more precisely over projective geometries).
, the three vertices in
V_{2}
were collinear. On the other hand, the parabola,
V_{2}
, has no collinear triples.
Most of the intersecting lines of the secants of
V_{1}
intersect
V_{2}
in two points, and we selected only one of them. Now we select a random subset, hoping that many lines will still intersect at a point as the number of points reduces. Let’s select points of
V_{2}
independently at random with probability
p
into a set
S
. The expected size of
S
is
pq
. The number of secants of
V_{1}
with two intersection points in
V_{2}
is
\frac{q(q-\chi(-1)-4)}{4}
, since we have to discard the tangents, the cases when the discriminant is zero, i.e. when
a-b=\pm 2
. We are looking for an asymptotic bound, so we will continue counting with
\approx q^{2}/4
such lines. The expected number of lines with at least one point in
S
is
(2p-p^{2})q^{2}/4
. Select
p
to maximize
\frac{(2p-p^{2})q^{2}/4}{(q+pq)^{2}}=\frac{2p-p^{2}}{4(1+p)^{2}}.
The maximum is achieved when
p=1/2
. Then the ratio is
1/12
as required. As the final step, we select the edges of the random subgraph of
\mathcal{H}
. If the line of the secant has four points, choose one of the two from
S
. The secants with one point in
S
determine a unique edge. Standard probability estimates (like Chernoff’s bounds and the union bound) show that there are sets
S\in V_{2}
that provide values close to the expected values.
∎