Forbidden paths and cycles in ordered graphs and matrices

DOI10.1007/BF02773960zbMath1132.05035MaRDI QIDQ2472738

János Pach, Gábor Tardos

Publication date: 22 February 2008

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

zbMATH Keywords

adjacency matrixforbidden patternsextremal problem for zero-one matrices

Mathematics Subject Classification ID

Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (35)

An exact characterization of saturation for permutation matrices ⋮ Counting ordered graphs that avoid certain subgraphs ⋮ Almost all permutation matrices have bounded saturation functions ⋮ Extremal problems for pairs of triangles ⋮ Tilings in vertex ordered graphs ⋮ Dirac-type results for tilings and coverings in ordered graphs ⋮ Interval Minors of Complete Bipartite Graphs ⋮ On the Turán number of some ordered even cycles ⋮ Excluded permutation matrices and the Stanley-Wilf conjecture ⋮ On the abstract chromatic number and its computability for finitely axiomatizable theories ⋮ On asymptotic packing of convex geometric and ordered graphs ⋮ Bipartite Turán problems for ordered graphs ⋮ Bounds on parameters of minimally nonlinear patterns ⋮ Degrees of nonlinearity in forbidden 0-1 matrix problems ⋮ Saturation of Ordered Graphs ⋮ Shadows of ordered graphs ⋮ Turán problems for edge-ordered graphs ⋮ Tight bounds on the maximum size of a set of permutations with bounded VC-dimension ⋮ Ordered Ramsey numbers ⋮ Equal entries in totally positive matrices ⋮ Semantic limits of dense combinatorial objects ⋮ On unit distances in a convex polygon ⋮ Ramsey numbers of ordered graphs ⋮ A tournament approach to pattern avoiding matrices ⋮ Partitioning ordered hypergraphs ⋮ Unnamed Item ⋮ On the Turán number of ordered forests ⋮ On the Turán number of ordered forests ⋮ Saturation Problems about Forbidden 0-1 Submatrices ⋮ On the chromatic number of disjointness graphs of curves ⋮ Ramsey numbers of interval 2-chromatic ordered graphs ⋮ Large Homogeneous Submatrices ⋮ Unnamed Item ⋮ Extremal problems for convex geometric hypergraphs and ordered hypergraphs ⋮ On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs

Cites Work

• Unnamed Item
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Extremal problems in discrete geometry
• Combinatorial complexity bounds for arrangements of curves and spheres
• Davenport-Schinzel theory of matrices
• On the self crossing six sided figure problem
• The maximum number of unit distances in a convex \(n\)-gon
• On the number of permutations avoiding a given pattern
• On 0-1 matrices and small excluded submatrices
• An Extremal Problem on Sparse 0-1 Matrices
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• On the structure of linear graphs

This page was built for publication: Forbidden paths and cycles in ordered graphs and matrices