Large Homogeneous Submatrices

DOI10.1137/19M125786XzbMath1460.05031arXiv1903.06608OpenAlexW3111352218MaRDI QIDQ5855527

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

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

forbidden submatrixErdős-Hajnal conjecturezero-one matricesintersection patterns

Mathematics Subject Classification ID

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

Related Items

Pure pairs. IV: Trees in bipartite graphs ⋮ Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix ⋮ Erdős-Hajnal-type results for monotone paths ⋮ Bipartite Independence Number in Graphs with Bounded Maximum Degree

Cites Work

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