Turán-Type Results for Complete h-Partite Graphs in Comparability and Incomparability Graphs
Change log
Authors
Abstract
We consider an h-partite version of Dilworth's theorem with multiple partial orders. Let P be a fi nite set, and let <₁, ..., <ᵣ be partial orders on P. Let G(P, <₁, ..., <ᵣ) be the graph whose vertices are the elements of P, and x, y ∈ P are joined by an edge if x <ᵢ y or y <ᵢ x holds for some 1 ≤ i ≤ r. We show that if the edge density of G(P, <₁, ..., <ᵣ) is strictly larger than 1 − 1/(2h − 2)ʳ , then P contains h disjoint sets A₁, ..., Aₕ such that A₁ <ⱼ ... <ⱼ Aₕ holds for some 1 ≤ j ≤ r, and |A₁| = ... = |Aₕ| = Ω(|P|).
Also, we show that if the complement of G(P, <) has edge density strictly larger than 1 − 1/(3h − 3), then P contains h disjoint sets A₁, ..., Aₕ such that the elements of Aᵢ are incomparable with the elements of Aⱼ for 1 ≤ i < j ≤ h, and |A₁| = ... = |Aₕ| = |P| ¹⁻ᵒ⁽¹⁾. Finally, we prove that if the edge density of the complement of G(P, <1, <2) is α, then there are disjoint sets A, B ⊂ P such that any element of A is incomparable with any element of B in both <₁ and <₂, and |A| = |B| > n¹⁻ᵞ⁽α⁾ , where γ(α) → 0 as α → 1.
We provide a few applications of these results in combinatorial geometry, as well.
Description
This is the final version of the article. It was first available from Springer via http://dx.doi.org/10.1007/s11083-015-9384-6
Keywords
Journal Title
Conference Name
Journal ISSN
1572-9273