The poset on connected graphs is Sperner

摘要

Let C be the set of all connected graphs on vertex set [n]. Then C is endowed with the following natural partial ordering: for G, H is an element of C, let G <= H if G is a subgraph of H. The poset (C, <=) is graded, each level containing the connected graphs with the same number of edges. We prove that (C, <=) has the Sperner property, namely that the largest antichain of (C, <=) is equal to its largest sized level. This answers a question of Katona. (C) 2017 Elsevier Inc. All rights reserved.