Subhypergraph counts in extremal and random hypergraphs and the fractional q-independence

Andrzej Dudek (), Joanna Polcyn () and Andrzej Ruciński ()
Additional contact information
Andrzej Dudek: Emory University
Joanna Polcyn: Adam Mickiewicz University
Andrzej Ruciński: Adam Mickiewicz University

Journal of Combinatorial Optimization, 2010, vol. 19, issue 2, No 5, 184-199

Abstract: 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.

Keywords: Hypergraphs; Fractional independence; Random hypergraphs (search for similar items in EconPapers)
Date: 2010
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-008-9174-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:19:y:2010:i:2:d:10.1007_s10878-008-9174-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-008-9174-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().