2013/02/25 by Victor Falgas‐Ravry, Victor Falgas-Ravry, Falgas-Ravry, Victor
Computer Science · Mathematics · #05C69 #05D05 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #G.2.1 #G.2.2 #Graph theory and applications #Limits and Structures in Graph Theory #acm:05C69 #acm:05D05 #math.CO #msc:05C69 #msc:05D05
paper · pdf · doi:10.48550/arxiv.1302.6039
26 pages
openalex publication_date 2013/02/25 · arxiv created 2013/10/07 · arxiv updated 2013/10/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 edge-less 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 the size of a maximal antichain is of the same order as the size of a largest layer of Q(G).