Note on a problem of M. Talagrand

作者：DeMarco B; Kahn J^*

来源：Random Structures and Algorithms, 2015, 47(4): 663-668.

DOI：10.1002/rsa.20559

• increasing family
• threshold
• fractional and integer optima
• p-small and weakly p-small

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 is an element of[0,1], if F is the set of subgraphs of K-n containing at least ((n)(k))p((2k)) copies of K-k, then there is a set G of subgraphs of K-n such that (i) each member of F contains a member of G and (ii) Sigma(S is an element of G)(p/L)(vertical bar S vertical bar) <= 1/2(where |S| means number of edges).

• 出版日期2015-12
• 单位rutgers