Combinatorial Nullstellensatz and Turán numbers of complete r-partite r-uniform hypergraphs

2023/07/10 by Alexey Gordeev, Gordeev, Alexey
Computer Science · Mathematics · #Advanced Graph Theory Research #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2307.04447

openalex publication_date 2023/07/10 · openalex created_date 2023/07/12 · openalex updated_date 2026/07/28

Abstract

In this note we describe how Lasoń's generalization of Alon's Combinatorial Nullstellensatz gives a framework for constructing lower bounds on the Turán number ex(n, K^(r)_s1,…,sr) of the complete r-partite r-uniform hypergraph K^(r)_s1,…,sr. To illustrate the potential of this method, we give a short and simple explicit construction for the Erdős box problem, showing that ex(n, K^(r)_2,…,2) = Ω(n^{r - 1/r}), which asymptotically matches best known bounds when r ≤ 4.

Related

• An alternative proof of the upper bound for the generalised Erdős box problem
• A short proof of a lower bound for Turán numbers
• Extremal constructions for apex partite hypergraphs
• A hypergraph bipartite Turán problem with odd uniformity
• Asymptotics of the hypergraph bipartite Turán problem