Sperner's problem for G-independent families
classification
🧮 math.CO
keywords
problemsizeantichaingraphlargestspernercasecollection
read the original 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 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).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.