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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom