A bipartite analogue of Dilworth's theorem

DOI10.1007/s11083-006-9043-zzbMath1108.06002OpenAlexW2039857505MaRDI QIDQ862983

Jacob Fox

Publication date: 25 January 2007

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11083-006-9043-z

zbMATH Keywords

Ramanujan graphconvex compact sets

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07)

Related Items

Clique-stable set separation in perfect graphs with no balanced skew-partitions ⋮ Excluding hooks and their complements ⋮ Turán-type results for partial orders and intersection graphs of convex sets ⋮ Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix ⋮ Pure pairs. X. Tournaments and the strong Erdős-Hajnal property ⋮ Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane ⋮ String graphs have the Erdős-Hajnal property ⋮ String graphs and incomparability graphs ⋮ Erdős-Hajnal-type results for monotone paths ⋮ Applications of a New Separator Theorem for String Graphs ⋮ A bipartite strengthening of the crossing Lemma ⋮ The reversal ratio of a poset. ⋮ A Separator Theorem for String Graphs and its Applications ⋮ A Separator Theorem for String Graphs and Its Applications ⋮ A Bipartite Strengthening of the Crossing Lemma ⋮ Pure pairs. II: Excluding all subdivisions of a graph ⋮ Turán-type results for complete \(h\)-partite graphs in comparability and incomparability graphs ⋮ A sharp threshold phenomenon in string graphs ⋮ Improved Ramsey-type results for comparability graphs ⋮ Ordered graphs and large bi-cliques in intersection graphs of curves ⋮ A bipartite analogue of Dilworth's theorem for multiple partial orders ⋮ Pure Pairs VI: Excluding an Ordered Tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• The strong perfect graph theorem
• A bipartite analogue of Dilworth's theorem for multiple partial orders
• Ramanujan graphs
• Eigenvalues and expanders
• Cubic Ramanujan graphs
• Some geometric applications of Dilworth's theorem
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Geometric graphs with few disjoint edges
• On a property of the class of n-colorable graphs
• Crossing patterns of semi-algebraic sets
• A decomposition theorem for partially ordered sets
• Ramsey graphs cannot be defined by real polynomials
• Good splitters for counting points in triangles
• A Ramsey-Type Result for Convex Sets
• Simulating independence
• Crossing patterns of segments
• The structure of Sperner k-families