On the average size of independent sets in triangle-free graphs

DOI10.1090/PROC/13728MaRDI QIDQ4590969zbMATHOpenAlexFDO

Authors Ewan Davies, Matthew Jenssen, Will Perkins, Barnaby Roberts

Publication date 21 November 2017

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Ramsey theoryhard-core modelindependent sets

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Generalized Ramsey theory (05C55) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We prove an asymptotically tight lower bound on the average size of independent sets in a triangle-free graph on $n$ vertices with maximum degree $d$, showing that an independent set drawn uniformly at random from such a graph has expected size at least $(1+o_d(1))fraclogddn$. This gives an alternative proof of Shearer's upper bound on the Ramsey number $R(3,k)$. We then prove that the total number of independent sets in a triangle-free graph with maximum degree $d$ is at least $expleft[left(frac12+o_d(1)ight)fraclo{g}^{2}ddnight]$. The constant $1/2$ in the exponent is best possible. In both cases, tightness is exhibited by a random $d$-regular graph. Both results come from considering the hard-core model from statistical physics: a random independent set $I$ drawn from a graph with probability proportional to $lambd{a}^{|I|}$, for a fugacity parameter $lambda>0$. We prove a general lower bound on the occupancy fraction (normalized expected size of the random independent set) of the hard-core model on triangle-free graphs of maximum degree $d$. The bound is asymptotically tight in $d$ for all $lambda=O_d(1)$. We conclude by stating several conjectures on the relationship between the average and maximum size of an independent set in a triangle-free graph and give some consequences of these conjectures in Ramsey theory.

Recommendations

• Counting independent sets in triangle-free graphs
• Occupancy fraction, fractional colouring, and triangle fraction
• Counting Independent Sets in Hypergraphs
• Dynamic concentration of the triangle-free process
• Independence, odd girth, and average degree

Cites work

• scientific article; zbMATH DE number 3951995 (Why is no real title available?)
• scientific article; zbMATH DE number 1789918 (Why is no real title available?)
• scientific article; zbMATH DE number 3185004 (Why is no real title available?)
• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs
• An entropy approach to the hard-core model on bipartite graphs
• An upper bound for the number of independent sets in regular graphs
• Counting Independent Sets in Hypergraphs
• Counting independent sets in triangle-free graphs
• Decay of correlations for the hardcore model on the \(d\)-regular random graph
• Dynamic concentration of the triangle-free process
• Graph colouring and the probabilistic method
• Independence numbers of locally sparse graphs and a Ramsey type problem
• Independent sets, matchings, and occupancy fractions
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• On independent sets in hypergraphs
• On the Ramsey numbers R(3,8) and R(3,9)
• On the independence number of sparse graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The number of independent sets in a regular graph
• The probabilistic method
• The triangle-free process and the Ramsey number \(R(3,k)\)

Cited in

(21)

• Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs
• The number of independent sets in an irregular graph
• Tight bounds on the coefficients of partition functions via stability
• Counting independent sets in triangle-free graphs
• Minimizing the number of independent sets in triangle-free regular graphs
• Counting proper colourings in 4-regular graphs via the Potts model
• A reverse Sidorenko inequality
• Occupancy fraction, fractional colouring, and triangle fraction
• Counting Independent Sets in Hypergraphs
• Graph and hypergraph colouring via nibble methods: a survey
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• On the average order of a dominating set of a forest
• Extremal regular graphs: independent sets and graph homomorphisms
• Two Conjectures in Ramsey--Turán Theory
• On the hard sphere model and sphere packings in high dimensions
• A tight upper bound on the average order of dominating sets of a graph
• Counting colorings of triangle-free graphs
• On the number of independent sets in uniform, regular, linear hypergraphs
• Counting independent sets in cubic graphs of given girth
• On kissing numbers and spherical codes in high dimensions
• The average size of independent sets of graphs

This page was built for publication: On the average size of independent sets in triangle-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4590969)