Turán-Type Results for Complete h-Partite Graphs in Comparability and Incomparability Graphs
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Nature
https://doi.org/10.1007/s11083-015-9384-6
https://doi.org/10.1007/s11083-015-9384-6
Abstract
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
We consider an h-partite version of Dilworth’s theorem with multiple partial orders. Let P be a finite set, and let <1,...,<r be partial orders on P. Let G(P, <1,...,<r) be the graph whose vertices are the elements of P, and x, y ∈ P are joined by an edge if x<iy or y<ix holds for some 1 ≤ i ≤ r. We show that if the edge density of G(P, <1, ... , <r) is strictly larger than 1 − 1/(2h − 2)r, then P contains h disjoint sets A1, ... , Ah such that A1 <j... <jAh holds for some 1 ≤ j ≤ r, and |A1| = ... = |Ah| = Ω(|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 A1, ... , Ah such that the elements of Ai are incomparable with the elements of Aj for 1 ≤ i < j ≤ h, and |A1| = ... = |Ah| = |P|1−o(1). 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 <1 and <2, and |A| = |B| > n1−γ(α), where γ(α) → 0 as α → 1. We provide a few applications of these results in combinatorial geometry, as well.
We consider an h-partite version of Dilworth’s theorem with multiple partial orders. Let P be a finite set, and let <1,...,<r be partial orders on P. Let G(P, <1,...,<r) be the graph whose vertices are the elements of P, and x, y ∈ P are joined by an edge if x<iy or y<ix holds for some 1 ≤ i ≤ r. We show that if the edge density of G(P, <1, ... , <r) is strictly larger than 1 − 1/(2h − 2)r, then P contains h disjoint sets A1, ... , Ah such that A1 <j... <jAh holds for some 1 ≤ j ≤ r, and |A1| = ... = |Ah| = Ω(|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 A1, ... , Ah such that the elements of Ai are incomparable with the elements of Aj for 1 ≤ i < j ≤ h, and |A1| = ... = |Ah| = |P|1−o(1). 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 <1 and <2, and |A| = |B| > n1−γ(α), where γ(α) → 0 as α → 1. We provide a few applications of these results in combinatorial geometry, as well.