Occupancy fraction, fractional colouring, and triangle fraction

Area of Science:

• Graph Theory
• Combinatorics
• Theoretical Computer Science

Background:

• Existing research by Ajtai, Komlós, and Szemerédi, and Shearer established bounds for graph properties.
• Understanding the structure of graphs with limited edge density in vertex neighborhoods is crucial.

Purpose of the Study:

• To establish new, stronger bounds on the size of random independent sets and the fractional chromatic number of graphs.
• To provide a theoretical framework that improves upon previous results in graph theory.

Main Methods:

• The study employs a tight analysis of the hard-core model.
• Mathematical proofs are used to derive theoretical bounds for graph parameters.

Main Results:

• For any graph with n vertices and maximum degree $\Delta$, if the neighborhood of each vertex spans at most $k$ edges, a randomly chosen independent set has at least $m$ vertices in expectation.
• Under the same conditions, the fractional chromatic number of the graph is at most $c$.

Conclusions:

• The derived bounds are asymptotically optimal, with potential improvements limited to a factor of 2.
• The results offer significant advancements in the understanding of graph properties and random structures within graphs.