Subhypergraph counts in extremal and random hypergraphs and the fractional q-independence
Authors:
- Andrzej Dudek,
- Joanna Polcyn-Lewandowska,
- Andrzej Ruciński
Abstract
We study the extremal parameter N(n,m,H) which is the largest number of copies of a hypergraph H that can be formed of at most n vertices and m edges. Generalizing previous work of Alon (Isr. J. Math. 38:116-130, 1981), Friedgut and Kahn (Isr. J. Math. 105:251-256, 1998) and Janson, Oleszkiewicz and the third author (Isr. J. Math. 142:61-92, 2004), we obtain an asymptotic formula for N(n,m,H) which is strongly related to the solution αq (H) of a linear programming problem, called here the fractional q-independence number of H. We observe that αq (H) is a piecewise linear function of q and determine it explicitly for some ranges of q and some classes of H. As an application, we derive exponential bounds on the upper tail of the distribution of the number of copies of H in a random hypergraph. © 2008 Springer Science+Business Media, LLC.
- Record ID
- UAM976f7c831b924c1e8edf84ae0d86267a
- Author
- Journal series
- Journal of Combinatorial Optimization, ISSN 1382-6905
- Issue year
- 2010
- Vol
- 19
- Pages
- 184-199
- ASJC Classification
- ; ; ; ;
- DOI
- DOI:10.1007/s10878-008-9174-9 Opening in a new tab
- Language
- (en) English
- Score (nominal)
- 0
- Score source
- journalList
- Publication indicators
- = 2; = 5; : 2010 = 1.194; : 2010 (2 years) = 0.843 - 2010 (5 years) =1.022
Share
- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM976f7c831b924c1e8edf84ae0d86267a/
- URN
urn:amu-prod:UAM976f7c831b924c1e8edf84ae0d86267a
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.