The poset of graphs ordered by induced containment

DOI10.1016/J.JCTA.2019.06.009MaRDI QIDQ2326334zbMATH OpenOpenAlexWikidataFDO

Authors Jason P. Smith

Publication date 7 October 2019

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

Full work available at URL https://arxiv.org/abs/1806.01821, https://strathprints.strath.ac.uk/69039/1/Smith_JCT_2019_The_poset_of_graphs_ordered_by_induced_containment.pdf

zbMATH Keywords

graph containmentMöbius functionposets

Mathematics Subject Classification ID

Graph theory (05C99) Combinatorics of partially ordered sets (06A07) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Abstract: We study the poset $mathcalG$ of all unlabelled graphs, up to isomorphism, with $HleG$ if $H$ occurs as an induced subgraph in $G$. We present some general results on the M"obius function of intervals of $mathcalG$ and some results for specific classes of graphs. This includes a case where the M"obius function is given by the Catalan numbers, which we prove using discrete Morse theory, and another case where it equals the Fibonacci numbers, therefore showing that the M"obius function is unbounded. A classification of the disconnected intervals of $mathcalG$ is presented, which gives a large class of non-shellable intervals. We also present several conjectures on the structure of $mathcalG$.

Recommendations

• The poset of unlabeled induced subgraphs of a finite graph
• The poset of mesh patterns
• On the Möbius function and topology of general pattern posets
• The Möbius function of the permutation pattern poset
• The Möbius function of a composition poset

Cites work

• A characterization of locally finite vertex-transitive graphs
• A formula for the Möbius function of the permutation poset based on a topological decomposition
• Combinatorial algebraic topology
• Definability in the substructure ordering of simple graphs
• Discrete Morse functions from lexicographic orders
• Graph minors. XX: Wagner's conjecture
• Graph theory
• Graph theory with applications
• scientific article; zbMATH DE number 4158687 (Why is no real title available?)
• scientific article; zbMATH DE number 17789 (Why is no real title available?)
• scientific article; zbMATH DE number 1139286 (Why is no real title available?)
• scientific article; zbMATH DE number 970688 (Why is no real title available?)
• Intervals of permutations with a fixed number of descents are shellable
• On the Möbius function and topology of general pattern posets
• On the topology of the permutation pattern poset
• Poset topology: tools and applications
• Shellable and Cohen-Macaulay Partially Ordered Sets
• The edge-subgraph poset of a graph and the edge reconstruction conjecture
• The Möbius function of a composition poset
• The Möbius function of separable and decomposable permutations
• The on-line encyclopedia of integer sequences
• The poset on connected graphs is Sperner

Cited in

(4)

• The order-interval hypergraph of a finite poset and the König property
• Möbius function for the set of acyclic directed backbone graphs.
• The poset of unlabeled induced subgraphs of a finite graph
• Containment Graphs, Posets, and Related Classes of Graphs

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: The poset of graphs ordered by induced containment

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