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

DOI10.1090/proc/13728zbMath1375.05194arXiv1606.01043OpenAlexW2416946508MaRDI QIDQ4590969

Barnaby Roberts, Will Perkins, Matthew Jenssen, Ewan Davies

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 theoryindependent setshard-core model

Mathematics Subject Classification ID

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

Related Items (18)

Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs ⋮ On kissing numbers and spherical codes in high dimensions ⋮ Extremal Regular Graphs: Independent Sets and Graph Homomorphisms ⋮ The average size of independent sets of graphs ⋮ Counting colorings of 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 ⋮ ON THE HARD SPHERE MODEL AND SPHERE PACKINGS IN HIGH DIMENSIONS ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Two Conjectures in Ramsey--Turán Theory ⋮ On the number of independent sets in uniform, regular, linear hypergraphs ⋮ Counting proper colourings in 4-regular graphs via the Potts model ⋮ 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 ⋮ A reverse Sidorenko inequality ⋮ On the average order of a dominating set of a forest

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decay of correlations for the hardcore model on the \(d\)-regular random graph
• An upper bound for the number of independent sets in regular graphs
• A note on the independence number of triangle-free graphs
• A note on Ramsey numbers
• On the Ramsey numbers R(3,8) and R(3,9)
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• An Entropy Approach to the Hard-Core Model on Bipartite Graphs
• Counting independent sets in triangle-free graphs
• The Number of Independent Sets in a Regular Graph
• Independence numbers of locally sparse graphs and a Ramsey type problem
• The Ramsey number R(3, t) has order of magnitude t²/log t
• On the independence number of sparse graphs
• The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)
• Independent sets, matchings, and occupancy fractions
• On independent sets in hypergraphs
• Dynamic concentration of the triangle-free process
• Counting Independent Sets in Hypergraphs
• Graph colouring and the probabilistic method

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