2024/02/21 by Im, Seonghyuk, Jiang, Suyun, Liu, Hong +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2402.13825
A well-known application of the dependent random choice asserts that any n-vertex graph G with positive edge density contains a `rich' vertex subset U of size n1-o(1) such that every pair of vertices in U has at least n1-o(1) common neighbors. In 2003, using a beautiful construction on hypercube, Kostochka and Sudakov showed that this is tight: one cannot remove the o(1) terms even if the edge density of G is 1/2. In this paper, we generalize their result from pairs to tuples. To be precise, we show that given every pair of positive integers p