Sperner's Problem for G-Independent Families. (15th October 2014)

• Record Type: Journal Article
• Authors: FALGAS-RAVRY, VICTOR
• Is Part Of: Combinatorics, probability and computing. Volume 24:Number 3(2015:May)
• Page Start: 528
• Page End: 550
• Publication Date: 2014-10-15
• Subjects: Primary 05D05; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000558
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : Given a graph G, let Q(G) denote the collection of all independent (edge-free) sets of vertices in G . We consider the problem of determining the size of a largest antichain in Q(G) . When G is the edgeless graph, this problem is resolved by Sperner's theorem. In this paper, we focus on the case where G is the path of length n − 1, proving that the size of a maximal antichain is of the same order as the size of a largest layer of Q(G) .