Repository logo
 

Turán-Type Results for Complete h-Partite Graphs in Comparability and Incomparability Graphs


Type

Article

Change log

Authors

Tomon, István 

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

4901 Applied Mathematics, 4904 Pure Mathematics, 49 Mathematical Sciences

Journal Title

Order

Conference Name

Journal ISSN

0167-8094
1572-9273

Volume Title

Publisher

Springer Science and Business Media LLC