Counterexamples to conjectures on the occupancy fraction of graphs

2023/11/09 by Cambie, Stijn, Jooken, Jorik · 1 citation
#05C07 #05C31 #05C35 #05C69 #68R05 #68R10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2311.05542

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) λ. We present a criterion for finding the graph with minimum occupancy fraction among graphs with a fixed order, and disprove five conjectures on the extremes of the occupancy fraction and (normalized) independence polynomial for certain graph classes of regular graphs with a given girth.

Cited by

• Computer-assisted graph theory: a survey

Related

• On expectations and variances in the hard-core model on bounded degree graphs
• Graph structure via local occupancy
• Independent sets in graphs with given minimum degree
• The average size of independent sets of graphs
• Approximately counting independent sets of a given size in bounded-degree graphs