Counterexamples to conjectures on the occupancy fraction of graphs
HTML articles powered by AMS MathViewer
- by Stijn Cambie and Jorik Jooken;
- Math. Comp.
- DOI: https://doi.org/10.1090/mcom/4121
- Published electronically: June 17, 2025
- HTML | PDF | Request permission
Abstract:
The occupancy fraction of a graph is a (normalized) measure on the size of independent sets under the hard-core model, depending on a variable (fugacity) $\lambda$. We present a criterion for finding the graph with minimum occupancy fraction among graphs with a fixed order. We computationally determine graphs having between 14 and 38 vertices that disprove five conjectures on the extremes of the occupancy fraction and (normalized) independence polynomial for certain graph classes of $d$-regular graphs with a given girth $g$.References
- Ivona Bezáková, Daniel Štefankovič, Vijay V. Vazirani, and Eric Vigoda, Accelerating simulated annealing for the permanent and combinatorial counting problems, SIAM J. Comput. 37 (2008), no. 5, 1429–1454. MR 2386275, DOI 10.1137/050644033
- S. Cambie and J. Jooken, Code and data for the paper “counterexamples to conjectures on the occupancy fraction of graphs”, https://github.com/JorikJooken/occupancyFraction, 2023.
- Emma Cohen, Péter Csikvári, Will Perkins, and Prasad Tetali, The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph, European J. Combin. 62 (2017), 70–76. MR 3621724, DOI 10.1016/j.ejc.2016.11.003
- Kris Coolsaet, Sven D’hondt, and Jan Goedgebeur, House of Graphs 2.0: a database of interesting graphs and more, Discrete Appl. Math. 325 (2023), 97–107. MR 4506063, DOI 10.1016/j.dam.2022.10.013
- Jonathan Cutler and A. J. Radcliffe, The maximum number of complete subgraphs in a graph with given maximum degree, J. Combin. Theory Ser. B 104 (2014), 60–71. MR 3132744, DOI 10.1016/j.jctb.2013.10.003
- Jonathan Cutler and A. J. Radcliffe, Minimizing the number of independent sets in triangle-free regular graphs, Discrete Math. 341 (2018), no. 3, 793–800. MR 3754392, DOI 10.1016/j.disc.2017.11.016
- Ewan Davies, Matthew Jenssen, Will Perkins, and Barnaby Roberts, Independent sets, matchings, and occupancy fractions, J. Lond. Math. Soc. (2) 96 (2017), no. 1, 47–66. MR 3687939, DOI 10.1112/jlms.12056
- David Galvin, Maximizing $H$-colorings of a regular graph, J. Graph Theory 73 (2013), no. 1, 66–84. MR 3031867, DOI 10.1002/jgt.21658
- David Galvin and Prasad Tetali, On weighted graph homomorphisms, Graphs, morphisms and statistical physics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 63, Amer. Math. Soc., Providence, RI, 2004, pp. 97–104. MR 2056231, DOI 10.1090/dimacs/063/07
- Derek Holt and Gordon Royle, A census of small transitive groups and vertex-transitive graphs, J. Symbolic Comput. 101 (2020), 51–60. MR 4109707, DOI 10.1016/j.jsc.2019.06.006
- Jeff Kahn, An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput. 10 (2001), no. 3, 219–237. MR 1841642, DOI 10.1017/S0963548301004631
- Markus Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30 (1999), no. 2, 137–146. MR 1665972, DOI 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G
- Guillem Perarnau and Will Perkins, Counting independent sets in cubic graphs of given girth, J. Combin. Theory Ser. B 133 (2018), 211–242. MR 3856710, DOI 10.1016/j.jctb.2018.04.009
- Ashwin Sah, Mehtaab Sawhney, David Stoner, and Yufei Zhao, A reverse Sidorenko inequality, Invent. Math. 221 (2020), no. 2, 665–711. MR 4121160, DOI 10.1007/s00222-020-00956-9
- Luke Sernau, Graph operations and upper bounds on graph homomorphism counts, J. Graph Theory 87 (2018), no. 2, 149–163. MR 3742175, DOI 10.1002/jgt.22148
- William Staton, Some Ramsey-type numbers and the independence ratio, Trans. Amer. Math. Soc. 256 (1979), 353–370. MR 546922, DOI 10.1090/S0002-9947-1979-0546922-6
- Yufei Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput. 19 (2010), no. 2, 315–320. MR 2593625, DOI 10.1017/S0963548309990538
- Yufei Zhao, Extremal regular graphs: independent sets and graph homomorphisms, Amer. Math. Monthly 124 (2017), no. 9, 827–843. MR 3722040, DOI 10.4169/amer.math.monthly.124.9.827
Bibliographic Information
- Stijn Cambie
- Affiliation: Department of Computer Science, KU Leuven Campus Kulak-Kortrijk, 8500 Kortrijk, Belgium
- MR Author ID: 1143002
- Email: stijn.cambie@hotmail.com
- Jorik Jooken
- Affiliation: Department of Computer Science, KU Leuven Campus Kulak-Kortrijk, 8500 Kortrijk, Belgium
- MR Author ID: 1511289
- ORCID: 0000-0002-5256-1921
- Email: jorik.jooken@kuleuven.be
- Received by editor(s): November 4, 2024
- Received by editor(s) in revised form: March 26, 2025
- Published electronically: June 17, 2025
- Additional Notes: This work was supported by FWO grants with grant numbers 1225224N and 1222524N
- © Copyright 2025 American Mathematical Society
- Journal: Math. Comp.
- MSC (2020): Primary 05C35, 05C07, 05C69
- DOI: https://doi.org/10.1090/mcom/4121