Independent sets, matchings, and occupancy fractions

DOI10.1112/jlms.12056zbMath1370.05160arXiv1508.04675OpenAlexW3124770589MaRDI QIDQ5357226

Will Perkins, Matthew Jenssen, Ewan Davies, Barnaby Roberts

Publication date: 14 September 2017

Published in: Journal of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

constrained optimization problems over distributions of random variablesmath formulad-regular graphs

Mathematics Subject Classification ID

Graph polynomials (05C31) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (26)

Matchings in regular graphs: minimizing the partition function ⋮ Extremal Regular Graphs: Independent Sets and Graph Homomorphisms ⋮ The average size of matchings in graphs ⋮ The average size of independent sets of graphs ⋮ On the average size of independent sets in triangle-free graphs ⋮ Occupancy fraction, fractional colouring, and triangle fraction ⋮ Graph and hypergraph colouring via nibble methods: a survey ⋮ Minimizing the number of independent sets in triangle-free regular graphs ⋮ Convergence of graphs with intermediate density ⋮ On the Widom–Rowlinson Occupancy Fraction in Regular Graphs ⋮ Maximizing the number of independent sets in claw-free cubic graphs ⋮ ON THE HARD SPHERE MODEL AND SPHERE PACKINGS IN HIGH DIMENSIONS ⋮ Independent sets in the middle two layers of Boolean lattice ⋮ Statistical Matching Theory ⋮ Counting independent sets in regular hypergraphs ⋮ On the number of independent sets in uniform, regular, linear hypergraphs ⋮ Independent sets in graphs ⋮ A proof of the upper matching conjecture for large graphs ⋮ Counting proper colourings in 4-regular graphs via the Potts model ⋮ The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph ⋮ Tight bounds on the coefficients of partition functions via stability ⋮ Counting independent sets in cubic graphs of given girth ⋮ The number of independent sets in an irregular graph ⋮ Number of \(A + B \neq C\) solutions in abelian groups and application to counting independent sets in hypergraphs ⋮ A reverse Sidorenko inequality ⋮ Independence polynomials of bipartite graphs

This page was built for publication: Independent sets, matchings, and occupancy fractions