pith. sign in

arxiv: 1302.6039 · v2 · pith:67RLFMPFnew · submitted 2013-02-25 · 🧮 math.CO

Sperner's problem for G-independent families

classification 🧮 math.CO
keywords problemsizeantichaingraphlargestspernercasecollection
0
0 comments X
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.