The poset of graphs ordered by induced containment

Jason P. Smith

Research output: Contribution to journalArticle

Abstract

We study the poset G of all unlabelled graphs with H≤G if H occurs as an induced subgraph in G. We present some general results on the Möbius function of intervals of G and some results for specific classes of graphs. This includes a case where the Möbius 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öbius function is unbounded. A classification of the disconnected intervals of G is presented, which gives a large class of non-shellable intervals. We also present several conjectures on the structure of G.

LanguageEnglish
Pages348-373
Number of pages26
JournalJournal of Combinatorial Theory. Series A
Volume168
Early online date4 Jul 2019
DOIs
Publication statusE-pub ahead of print - 4 Jul 2019

Fingerprint

Möbius Function
Poset
Interval
Graph in graph theory
Discrete Morse Theory
Catalan number
Lame number
Induced Subgraph
Class

Keywords

  • graph containment
  • Möbius function
  • posets
  • combinatorial theory

Cite this

@article{349a59046c3849cda5773d7c24bd1bbb,
title = "The poset of graphs ordered by induced containment",
abstract = "We study the poset G of all unlabelled graphs with H≤G if H occurs as an induced subgraph in G. We present some general results on the M{\"o}bius function of intervals of G and some results for specific classes of graphs. This includes a case where the M{\"o}bius 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{\"o}bius function is unbounded. A classification of the disconnected intervals of G is presented, which gives a large class of non-shellable intervals. We also present several conjectures on the structure of G.",
keywords = "graph containment, M{\"o}bius function, posets, combinatorial theory",
author = "Smith, {Jason P.}",
year = "2019",
month = "7",
day = "4",
doi = "10.1016/j.jcta.2019.06.009",
language = "English",
volume = "168",
pages = "348--373",
journal = "Journal of Combinatorial Theory Series A",
issn = "0097-3165",

}

The poset of graphs ordered by induced containment. / Smith, Jason P.

In: Journal of Combinatorial Theory. Series A, Vol. 168, 30.11.2019, p. 348-373.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The poset of graphs ordered by induced containment

AU - Smith, Jason P.

PY - 2019/7/4

Y1 - 2019/7/4

N2 - We study the poset G of all unlabelled graphs with H≤G if H occurs as an induced subgraph in G. We present some general results on the Möbius function of intervals of G and some results for specific classes of graphs. This includes a case where the Möbius 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öbius function is unbounded. A classification of the disconnected intervals of G is presented, which gives a large class of non-shellable intervals. We also present several conjectures on the structure of G.

AB - We study the poset G of all unlabelled graphs with H≤G if H occurs as an induced subgraph in G. We present some general results on the Möbius function of intervals of G and some results for specific classes of graphs. This includes a case where the Möbius 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öbius function is unbounded. A classification of the disconnected intervals of G is presented, which gives a large class of non-shellable intervals. We also present several conjectures on the structure of G.

KW - graph containment

KW - Möbius function

KW - posets

KW - combinatorial theory

UR - http://www.scopus.com/inward/record.url?scp=85068251243&partnerID=8YFLogxK

U2 - 10.1016/j.jcta.2019.06.009

DO - 10.1016/j.jcta.2019.06.009

M3 - Article

VL - 168

SP - 348

EP - 373

JO - Journal of Combinatorial Theory Series A

T2 - Journal of Combinatorial Theory Series A

JF - Journal of Combinatorial Theory Series A

SN - 0097-3165

ER -