The poset on connected graphs is Sperner

DOI10.1016/J.JCTA.2017.03.003MaRDI QIDQ2397104zbMATH OpenOpenAlexFDO

Authors Stephen G. Z. Smith, István Tomon

Publication date 29 May 2017

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.08246

zbMATH Keywords

connected graphsposetsSperner's theorem

Mathematics Subject Classification ID

Connectivity (05C40) Combinatorics of partially ordered sets (06A07)

Abstract: Let $mathcalG$ be the set of all connected graphs on vertex set $[n]$. Define the partial ordering $<$ on $mathcalG$ as follows: for $G,HinmathcalG$ let $G<H$ if $E(G)subsetE(H)$. The poset $(mathcalG,<)$ is graded, each level containing the connected graphs with the same number of edges. We prove that $(mathcalG,<)$ has the Sperner property, namely that the largest antichain of $(mathcalG,<)$ is equal to its largest sized level.

Recommendations

• The poset on connected induced subgraphs of a graph need not be Sperner
• scientific article; zbMATH DE number 3861193
• Polygonal graphs as ordered sets: the Sperner criterion
• scientific article; zbMATH DE number 3851159
• scientific article; zbMATH DE number 3877243

Cites work

• Analytic combinatorics
• scientific article; zbMATH DE number 3974960 (Why is no real title available?)
• scientific article; zbMATH DE number 3489128 (Why is no real title available?)
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• scientific article; zbMATH DE number 3189757 (Why is no real title available?)
• On Representatives of Subsets
• The poset on connected induced subgraphs of a graph need not be Sperner

Cited in

(9)

• The poset on connected induced subgraphs of a graph need not be Sperner
• The poset of graphs ordered by induced containment
• Infinitely many trees have non-Sperner subtree poset
• Polygonal graphs as ordered sets: the Sperner criterion
• SPN graphs: when copositive = SPN
• scientific article; zbMATH DE number 3861193 (Why is no real title available?)
• scientific article; zbMATH DE number 1139286 (Why is no real title available?)
• scientific article; zbMATH DE number 1792666 (Why is no real title available?)
• Sperner's problem for \(G\)-independent families

This page was built for publication: The poset on connected graphs is Sperner

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397104)