Partitioning ordered hypergraphs

DOI10.1016/J.JCTA.2020.105300zbMATH Open1448.05161arXiv1906.03342OpenAlexW3047189704MaRDI QIDQ2005178FDOQ2005178

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

Publication date: 7 October 2020

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: An {em ordered $r$-graph} is an $r$-uniform hypergraph whose vertex set is linearly ordered. Given $2leqkleqr$, an ordered $r$-graph $H$ is {em interval} $k$-{em partite} if there exist at least $k$ disjoint intervals in the ordering such that every edge of $H$ has nonempty intersection with each of the intervals and is contained in their union. Our main result implies that for each $alpha>k-1$ and $d>0$, every $n$-vertex ordered $r$-graph with $d,n^{alpha}$ edges has for some $mleqn$ an $m$-vertex interval $k$-partite subgraph with $Omega(d,m^{alpha})$ edges. This is an extension to ordered $r$-graphs of the observation by ErdH os and Kleitman that every $r$-graph contains an $r$-partite subgraph with a constant proportion of the edges. The restriction $alpha>k-1$ is sharp. We also present applications of the main result to several extremal problems for ordered hypergraphs.

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

Recommendations

• Complete \(r\)-partite subgraphs of dense \(r\)-graphs
• Partition critical hypergraphs
• On the number of linear multipartite hypergraphs with given size
• On judicious partitions of uniform hypergraphs
• Partitioning dense uniform hypergraphs

zbMATH Keywords

interval \(k\)-partite hypergraphsordered hypergraphsTurán problem

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Title not available (Why is that?)
• Exact solution of some Turán-type problems
• Davenport-Schinzel theory of matrices
• Forbidden paths and cycles in ordered graphs and matrices
• Extensions of the linear bound in the Füredi-Hajnal conjecture
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Proof of a conjecture of Erdős on triangles in set-systems
• Forbidden submatrices
• A survey of forbidden configuration results
• The maximum number of unit distances in a convex \(n\)-gon
• On coloring graphs to maximize the proportion of multicolored k-edges
• On 0-1 matrices and small excluded submatrices
• An Extremal Problem on Sparse 0-1 Matrices
• An Extremal Set-Intersection Theorem
• The junta method in extremal hypergraph theory and Chvátal's conjecture
• A survey of Turán problems for expansions
• New results on simplex-clusters in set systems
• Extremal problems for convex geometric hypergraphs and ordered hypergraphs
• Tight paths in convex geometric hypergraphs

Cited In (6)

• Hypergraph Partitioning-Based Fill-Reducing Ordering for Symmetric Matrices
• Partitioning a weighted partial order
• Partitioning subgraphs of profinite ordered graphs
• Combinatorial optimization of special graphs for nodal ordering and graph partitioning
• Title not available (Why is that?)
• Extremal problems for convex geometric hypergraphs and ordered hypergraphs

This page was built for publication: Partitioning ordered hypergraphs

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