Sperner's Problem for G-Independent Families. (15th October 2014) - FALGAS-RAVRY, VICTOR
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) .