On Betti numbers of flag complexes with forbidden induced subgraphs

DOI10.1017/S030500411900001XMaRDI QIDQ5115548zbMATH OpenWikidataFDO

Authors Karim Adiprasito, Eran Nevo, Martin Tancer

Publication date 16 August 2020

Published in Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

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

zbMATH Keywords

Betti numbers of clique complexessuperpolynomial upper bound

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Combinatorial aspects of simplicial complexes (05E45) Relations of low-dimensional topology with graph theory (57M15)

Abstract: We analyze the asymptotic extremal growth rate of the Betti numbers of clique complexes of graphs on n vertices not containing a fixed forbidden induced subgraph H. In particular, we prove a theorem of the alternative: for any H the growth rate achieves exactly one of five possible exponentials, that is, independent of the field of coefficients, the nth root of the maximal total Betti number over n-vertex graphs with no induced copy of H has a limit, as n tends to infinity, and, ranging over all H, exactly five different limits are attained. For the interesting case where H is the 4-cycle, the above limit is 1, and we prove a slightly superpolynomial upper bound.

Recommendations

• Extremal problems related to Betti numbers of flag complexes
• Forbidden induced bipartite graphs
• Excluding Induced Subgraphs III: A General Asymptotic
• On Graded Betti Numbers of a Class of Graphs
• Characteristic-independence of Betti numbers of graph ideals

Cites work

• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• A construction of hyperbolic Coxeter groups.
• A course in combinatorics.
• Excluding induced subgraphs
• Extremal problems related to Betti numbers of flag complexes
• Graph theory
• Hyperbolic Coxeter groups of large dimension.
• Invitation to discrete mathematics
• Ramsey-type theorems
• Simplicial nonpositive curvature
• The Erdős-Hajnal conjecture. A survey
• The asymptotic number of graphs not containing a fixed color-critical subgraph

Cited in

(1)

• Extremal problems related to Betti numbers of flag complexes

This page was built for publication: On Betti numbers of flag complexes with forbidden induced subgraphs

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