Extremal problems for convex geometric hypergraphs and ordered hypergraphs

DOI10.4153/S0008414X20000632MaRDI QIDQ5021260zbMATH OpenOpenAlexFDO

Authors Tao Jiang, Dhruv Mubayi, J. Verstraëte, Zoltán Füredi, Alexandr Kostochka

Publication date 12 January 2022

Published in Canadian Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.04575

zbMATH Keywords

convex geometric hypergraphextremal hypergraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Extremal set theory (05D05) Erd?s problems and related topics of discrete geometry (52C10)

Abstract: An ordered hypergraph is a hypergraph whose vertex set is linearly ordered, and a convex geometric hypergraph is a hypergraph whose vertex set is cyclically ordered. Extremal problems for ordered and convex geometric graphs have a rich history with applications to a variety of problems in combinatorial geometry. In this paper, we consider analogous extremal problems for uniform hypergraphs, and determine the order of magnitude of the extremal function for various ordered and convex geometric paths and matchings. Our results generalize earlier works of Bra{ss}-K'{a}rolyi-Valtr, Capoyleas-Pach and Aronov-Dujmoviv{c}-Morin-Ooms-da Silveira. We also provide a new generalization of the ErdH os-Ko-Rado theorem in the ordered setting.

Recommendations

• scientific article; zbMATH DE number 2145227
• Extremal problems for ordered hypergraphs: small patterns and some enumeration
• Polytopes determined by hypergraph classes
• Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences
• Tight paths in convex geometric hypergraphs

Cites work

• A Turán-type theorem on chords of a convex polygon
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Extremal theory for convex matchings in convex geometric graphs
• Forbidden paths and cycles in ordered graphs and matrices
• How many unit equilateral triangles can be generated by N points in convex position?
• scientific article; zbMATH DE number 2145227 (Why is no real title available?)
• scientific article; zbMATH DE number 2209719 (Why is no real title available?)
• scientific article; zbMATH DE number 3198027 (Why is no real title available?)
• More Turán-type theorems for triangles in convex point sets
• On coloring graphs to maximize the proportion of multicolored k-edges
• On the Turán number of ordered forests
• Ordered and convex geometric trees with linear extremal function
• Partitioning ordered hypergraphs
• Tight paths in convex geometric hypergraphs
• Triangles of extremal area or perimeter in a finite planar point set

Cited in

(13)

• Extremal problems for ordered hypergraphs: small patterns and some enumeration
• Partitioning ordered hypergraphs
• Extremal problems for pairs of triangles
• Tilings in vertex ordered graphs
• Ordered and convex geometric trees with linear extremal function
• Saturation problems in convex geometric hypergraphs
• The geometry of convex affine maximal graphs
• scientific article; zbMATH DE number 2145227 (Why is no real title available?)
• Helly-type theorems for the ordering of the vertices of a hypergraph
• Ordered unavoidable sub-structures in matchings and random matchings
• Turán numbers of ordered tight hyperpaths
• Extremal, enumerative and probabilistic results on ordered hypergraph matchings
• Largest bipartite sub-matchings of a random ordered matching or a problem with socks

This page was built for publication: Extremal problems for convex geometric hypergraphs and ordered hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5021260)