The edge-statistics conjecture for ℓ ≪ k6/5

Let k and ℓ be positive integers. We prove that if 1 ≤ ℓ ≤ O k ( k 6/5 ), then in every large enough graph G , the fraction of k -vertex subsets that induce exactly ℓ edges is at most 1/ e + o k (1). Together with a recent result of Kwan, Sudakov and Tran, this settles a conjecture of Alon, Hefetz,...

Full description

Saved in:
Bibliographic Details
Published in:Israel journal of mathematics 2019-10, Vol.234 (2), p.677-690
Main Authors: Martinsson, Anders, Mousset, Frank, Noever, Andreas, Trujić, Miloš
Format: Article
Language:English
Subjects:
Algebra
Analysis
Applications of Mathematics
Group Theory and Generalizations
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let k and ℓ be positive integers. We prove that if 1 ≤ ℓ ≤ O k ( k 6/5 ), then in every large enough graph G , the fraction of k -vertex subsets that induce exactly ℓ edges is at most 1/ e + o k (1). Together with a recent result of Kwan, Sudakov and Tran, this settles a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn.
ISSN:0021-2172
1565-8511
DOI:10.1007/s11856-019-1929-8