The poset on connected graphs is Sperner
The poset on connected graphs is Sperner
复制标题
连通图上的偏序集是 Sperner
DOI：
10.1016/j.jcta.2017.03.003
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
István Tomon
中科院分区：
文献类型：
--
作者：
Stephen G. Z. Smith;István Tomon
设C是顶点集[n]上所有连通图的集合。则C被赋予如下自然偏序：对于G，H∈C，令G≤H如果G是H的一个子图。偏序集(C，≤)是分次的，每一层包含具有相同边数的连通图。我们证明了(C，≤)具有Sperner性质，即(C，≤)的最大反链等于其最大尺度级。这回答了卡托纳的一个问题。
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∈ 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.