Source author record

Laszlo A. Szekely

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

A new asymptotic enumeration technique: the Lovasz Local Lemma

Our previous paper applied a lopsided version of the Lovász Local Lemma that allows negative dependency graphs to the space of random injections from an $m$ -element set to an $n$ -element set. Equivalently, the same story can be told about the space of random matchings in $K_{n,m}$ . Now we show how the cited version of the Lovász Local Lemma applies to the space of random matchings in $K_{2n}$ . We also prove tight upper bounds that asymptotically match the lower bound given by the Lovász Local Lemma. As a consequence, we give new proofs to results on the enumeration of $d$ -regular graphs. The tight upper bounds can be modified to the space of matchings in $K_{n,m}$ , where they yield as application asymptotic formulas for permutation and Latin rectangle enumeration problems. The strength of the method is shown by a new result: enumeration of graphs by degree sequence or bipartite degree sequence and girth. As another application, we provide a new proof to the classical probabilistic result of Erd\H os that showed the existence of graphs with arbitrary large girth and chromatic number. If the degree sequence satisfies some mild conditions, almost all graphs with this degree sequence and prescribed girth have high chromatic number.

preprint2011arXiv

Asymptotically normal distribution of some tree families relevant for phylogenetics, and of partitions without singletons

P.L. Erdos and L.A. Szekely [Adv. Appl. Math. 10(1989), 488-496] gave a bijection between rooted semilabeled trees and set partitions. L.H. Harper's results [Ann. Math. Stat. 38(1967), 410-414] on the asymptotic normality of the Stirling numbers of the second kind translates into asymptotic normality of rooted semilabeled trees with given number of vertices, when the number of internal vertices varies. The Erdos-Szekely bijection specializes to a bijection between phylogenetic trees and set partitions with classes of size \geq 2. We consider modified Stirling numbers of the second kind that enumerate partitions of a fixed set into a given number of classes of size \geq 2, and obtain their asymptotic normality as the number of classes varies. The Erdos- Szekely bijection translates this result into the asymptotic normality of the number of phylogenetic trees with given number of vertices, when the number of leaves varies. We also obtain asymptotic normality of the number of phylogenetic trees with given number of leaves and varying number of internal vertices, which make more sense to students of phylogeny. By the Erdos-Szekely bijection this means the asymptotic normality of the number of partitions of n + m elements into m classes of size \geq 2, when n is fixed and m varies. The proofs are adaptations of the techniques of L.H. Harper [ibid.]. We provide asymptotics for the relevant expectations and variances with error term O(1/n).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.