Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-17T02:13:07.519Z Has data issue: false hasContentIssue false
  • English
  • Français

On Betti numbers of flag complexes with forbidden induced subgraphs

Part of: Graph theory Low-dimensional topology Algebraic combinatorics

Published online by Cambridge University Press:  07 June 2019

KARIM ADIPRASITO ,
ERAN NEVO  and
MARTIN TANCER
KARIM ADIPRASITO*
Affiliation:
Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem, 91904 Israel.
ERAN NEVO
Affiliation:
Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem, 91904 Israel.
MARTIN TANCER
Affiliation:
Department of Applied Mathematics, Charles University in Prague, Malostranské náměstí 25, 118 00, Praha 1. e-mail: [email protected]
*
e-mails: [email protected], [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We analyse 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 superpolynomial upper bound.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05E45: Combinatorial aspects of simplicial complexes 57M15: Relations with graph theory
Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 168 , Issue 3 , May 2020 , pp. 567 - 600
Copyright
Copyright © Cambridge Philosophical Society 2019

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

Supported by ERC-2016-STG 716424 - CASe and Israel Science Foundation grant 1050/16.

‡

Partially supported by Israel Science Foundation grants ISF-805/11, ISF-1695/15, by grant 2528/16 of the ISF-NRF Singapore joint research program, and by ISF-BSF joint grant 2016288.

§

Partially supported by the GAČR grant 16-01602Y and by Charles University project UNCE/SCI/004. Part of this work was done when M. T. was affiliated with IST Austria.

References

REFERENCES

Adamaszek, M.. Extremal problems related to Betti numbers of flag complexes. Discrete Appl. Math. 173 (2014), 8–15.CrossRefGoogle Scholar
Chudnovsky, M.. The Erdös–Hajnal conjecture—a survey. J. Graph Theory 75 (2014), no. 2, 178–190.CrossRefGoogle Scholar
Chudnovsky, M. and Seymour, P.. Excluding induced subgraphs. Surveys in combinatorics 2007. London Math. Soc. Lecture Note Ser., vol. 346. (Cambridge University Press, Cambridge, 2007), pp. 99–119.Google Scholar
Diestel, R.. Graph theory, fifth ed. Graduate Texts in Math, vol. 173. (Springer, Berlin, 2017).CrossRefGoogle Scholar
Erdős, P. and Hajnal, A.. Ramsey-type theorems, Discrete Appl. Math. 25 (1989), no. 1-2, 37–52. Combinatorics and complexity (Chicago, IL, 1987).CrossRefGoogle Scholar
Fekete, M., Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten. Math. Z. 17 (1923), 228–249.CrossRefGoogle Scholar
Januszkiewicz, T. and Świa̦tkowski, J., Hyperbolic Coxeter groups of large dimension, Comment. Math. Helv. 78 (2003), no. 3, 555–583.CrossRefGoogle Scholar
Januszkiewicz, T. and Świa̦tkowski, J., Simplicial nonpositive curvature. Publ. Math. Inst. Hautes Études Sci. (2006), no. 104, 1–85.CrossRefGoogle Scholar
Král’, D., Kratochvíl, J., Tuza, Z., and J., G. Woeginger. Graph-theoretic concepts in computer science: 27th International Workshop, WG 2001 Boltenhagen, Germany, June 14–16, 2001 proceedings. (Springer Berlin Heidelberg, Berlin, Heidelberg, 2001), pp. 254–262.CrossRefGoogle Scholar
Matoušek, J. and Nešetřil, J.. Invitation to Discrete Mathematics, second ed. (Oxford University Press, Oxford, 2009).Google Scholar
Osajda, D.. A construction of hyperbolic Coxeter groups. Comment. Math. Helv. 88 (2013), no. 2, 353–367.CrossRefGoogle Scholar
Prömel, H. J. and Steger, A., The asymptotic number of graphs not containing a fixed colour-critical subgraph. Combinatorica 12 (1992), no. 4, 463–473.CrossRefGoogle Scholar
Van Lint, J. H. and Wilson, R. M., A Course in Combinatorics, second ed. (Cambridge University Press, Cambridge, 2001).CrossRefGoogle Scholar