Article in volume
Authors:
Mahdieh Hasheminezhad
Department of Computer Science
Yazd University, Yazd, Iran
Combinatorial and Geometric Algorithms Lab
email: hasheminezhadl@yazd.ac.ir
Brendan D. McKay
Research School of Computer Science
Australian National University, Canberra, ACT 2601, Australia
email: brendan.mckay@anu.edu.au
Title:
Asymptotic enumeration of non-uniform linear hypergraphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(1) (2022) 219-230
Received: 2019-01-12 , Revised: 2019-09-21 , Accepted: 2019-09-21 , Available online: 2019-11-02 , https://doi.org/10.7151/dmgt.2246
Abstract:
A linear hypergraph, also known as a partial Steiner system, is a collection
of subsets of a set such that no two of the subsets have more than one element
in common. Most studies of linear hypergraphs consider only the uniform case,
in which all the subsets have the same size. In this paper we provide, for the
first time, asymptotically precise estimates of the number of linear hypergraphs
in the non-uniform case, as a function of the number of subsets of each size.
Keywords:
Steiner system, linear hypergraph, asymptotic enumeration, switching method
References:
- V. Blinovsky and C. Greenhill, Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees, Electron. J. Combin. 23 (2016) #P3.17.
https://doi.org/10.37236/5512 - D.A. Grable and K.T. Phelps, Random methods in design theory: A survey, J. Combin. Des. 4 (1996) 255–273.
https://doi.org/10.1002/(SICI)1520-6610(1996)4:4<255::AID-JCD4>3.0.CO;2-E - C. Greenhill, B.D. McKay and X. Wang, Asymptotic enumeration of sparse $0-1$ matrices with irregular row and column sums, J. Combin. Theory Ser. A 113 (2006) 291–324.
https://doi.org/10.1016/j.jcta.2005.03.005 - B.D. McKay and Fang Tian, Asymptotic enumeration of linear hypergraphs with given number of vertices and edges (2019).
arXiv: 1908.06333 - R.M. Wilson, An existence theory for pairwise balanced designs, III: Proof of the existence conjectures, J. Combin. Theory Ser. A 18 (1975) 71–79.
https://doi.org/10.1016/0097-3165(75)90067-9
Close