Large homogeneous submatrices

DOI10.1137/19M125786XMaRDI QIDQ5855527zbMATH OpenOpenAlexFDO

Authors Dániel Korándi, János Pach, István Tomon

Publication date 18 March 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Erdős-Hajnal conjectureforbidden submatrixintersection patternszero-one matrices

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Ramsey theory (05D10) Combinatorics of partially ordered sets (06A07) Boolean and Hadamard matrices (15B34) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Abstract: A matrix is homogeneous if all of its entries are equal. Let $P$ be a $2imes2$ zero-one matrix that is not homogeneous. We prove that if an $nimesn$ zero-one matrix $A$ does not contain $P$ as a submatrix, then $A$ has an $cnimescn$ homogeneous submatrix for a suitable constant $c>0$. We further provide an almost complete characterization of the matrices $P$ (missing only finitely many cases) such that forbidding $P$ in $A$ guarantees an $n^{1-o(1)}imes{n}^{1-o(1)}$ homogeneous submatrix. We apply our results to chordal bipartite graphs, totally balanced matrices, halfplane-arrangements and string graphs.

Recommendations

• Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix
• On the number of homogeneous subgraphs of a graph
• Forbidden submatrices
• On forbidden submatrices
• The number of submatrices of a given type in a Hadamard matrix and related results

Cites work

• A bipartite analogue of Dilworth's theorem for multiple partial orders
• A survey of forbidden configuration results
• An abstract approach to polychromatic coloring: shallow hitting sets in ABA-free hypergraphs and pseudohalfplanes
• Caterpillars in Erdős-Hajnal
• Characterizations of totally balanced matrices
• Crossing patterns of semi-algebraic sets
• Davenport-Schinzel theory of matrices
• Doubly Lexical Orderings of Matrices
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Forbidden paths and cycles in ordered graphs and matrices
• How many ways can one draw a graph?
• scientific article; zbMATH DE number 3851153 (Why is no real title available?)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 3628985 (Why is no real title available?)
• scientific article; zbMATH DE number 5035595 (Why is no real title available?)
• scientific article; zbMATH DE number 3279789 (Why is no real title available?)
• Improved Ramsey-type results for comparability graphs
• Intersection patterns of curves
• Large homogeneous subgraphs in bipartite graphs with forbidden induced subgraphs
• On s -intersecting curves and related problems
• On the Turán number of ordered forests
• On universality of graphs with uniformly distributed edges
• Perfect Elimination and Chordal Bipartite Graphs
• Permuting matrices to avoid forbidden submatrices
• Pure pairs. I: Trees and linear anticomplete pairs
• Ramsey-type theorems
• Small forbidden configurations. IV: The 3 rowed case
• String graphs and incomparability graphs
• The Erdős-Hajnal conjecture for paths and antipaths
• The Erdős-Hajnal conjecture. A survey
• The maximum number of unit distances in a convex n-gon
• Totally-Balanced and Greedy Matrices

Cited in

(6)

• Erdős-Hajnal-type results for monotone paths
• Bipartite independence number in graphs with bounded maximum degree
• Pure pairs. IV: Trees in bipartite graphs
• Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix
• A multipartite analogue of Dilworth's theorem
• A structure theorem for pseudosegments and its applications

This page was built for publication: Large homogeneous submatrices

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