Sperner's Problem for G-Independent Families
2015 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 24, no 3, 528-550 p.Article in journal (Refereed) Published
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).
Place, publisher, year, edition, pages
2015. Vol. 24, no 3, 528-550 p.
IdentifiersURN: urn:nbn:se:umu:diva-106332DOI: 10.1017/S0963548314000558ISI: 000356495300005OAI: oai:DiVA.org:umu-106332DiVA: diva2:841990