Maximum star densities

Abstract

Given an integer $k\ge 2$ and a real number $\gamma \in [0,1]$, which graphs of edge density $\gamma$ contain the largest number of $k$-edge stars? For $k=2$ Ahlswede and Katona proved that asymptotically there cannot be more such stars than in a clique or in the complement of a clique (depending on the value of $\gamma$). Here we extend their result to all integers $k\ge 2$.

third version addresses changes arising from the referee reports

References in corpus (2)

• An information theoretic approach to Sidorenko's conjecture
• On the logarithimic calculus and Sidorenko's conjecture

Cited by in corpus (2)

• The feasible region of induced graphs
• Threshold Graphs Maximize Homomorphism Densities