Premium
Note on a problem of M. Talagrand
Author(s) -
DeMarco B.,
Kahn J.
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20559
Subject(s) - combinatorics , struct , property (philosophy) , set (abstract data type) , mathematics , discrete mathematics , computer science , philosophy , epistemology , programming language
Answering a question of M. Talagrand, we show that there is a fixed L with the following property. For positive integers k ≤ n and p ∈ [ 0 , 1 ] , if ℱ is the set of subgraphs of K n containing at least(nk) p (k2)copies of K k , then there is a set G of subgraphs of K n such that (i) each member of ℱ contains a member of G and (ii)∑ S ∈ G( p / L ) | S |≤ 1 / 2 (where | S | means number of edges). © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 663–668, 2015