Improved bounds on the extremal function of hypergraphs

2018/07/05 by William Zhang, Zhang, William
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1807.02411

openalex publication_date 2018/07/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A fundamental problem in pattern avoidance is describing the asymptotic behavior of the extremal function and its generalizations. We prove an equivalence between the asymptotics of the graph extremal function for a class of bipartite graphs and the asymptotics of the matrix extremal function. We use the equivalence to prove several new bounds on the extremal functions of graphs. We develop a new method to bound the extremal function of hypergraphs in terms of the extremal function of their associated multidimensional matrices, improving the bound of the extremal function of d-permutation hypergraphs of length k from O(n^d-1) to 2^O(k)n^d-1.

Related

• Extremal problems for ordered hypergraphs: small patterns and some enumeration
• Extremal problems for ordered (hyper)graphs: applications of Davenport-Schinzel sequences
• Extremal Functions of Forbidden Multidimensional Matrices
• Linear bounds on matrix extremal functions using visibility hypergraphs
• Extremal aspects of graph and hypergraph decomposition problems