On Betti numbers of flag complexes with forbidden induced subgraphs

DOI10.1017/S030500411900001XzbMATH Open1445.05053arXiv1602.01761WikidataQ127776552 ScholiaQ127776552MaRDI QIDQ5115548FDOQ5115548

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)

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.

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

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

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)

Cites Work

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

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)