2003/05/01 by Martin Klazar, Klazar, Martin · 1 citation
Computer Science · Mathematics · #05D05 (Primary) 05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05C35 #msc:05D05
paper · pdf · doi:10.48550/arxiv.math/0305037
22 pages, submitted to the European Journal of Combinatorics
arxiv created 2003/05/01 · openalex publication_date 2003/05/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a containment relation of hypergraphs which respects linear orderings of vertices and investigate associated extremal functions. We extend, by means of a more generally applicable theorem, the n.log n upper bound on the ordered graph extremal function of F=(1,3, 1,5, 2,3, 2,4) due to Z. Furedi to the n.(log n)2.(loglog n)3 upper bound in the hypergraph case. We use Davenport-Schinzel sequences to derive almost linear upper bounds in terms of the inverse Ackermann function. We obtain such upper bounds for the extremal functions of forests consisting of stars whose all centers precede all leaves.