Search

We consider the binomial random set model $[n]_p$ where each element in $\{1,\dots,n\}$ is chosen independently with probability $p:=p(n)$. We show that for essentially all regimes of $p$ and very general conditions for a matrix $A$ and a column vector $\mathbf{b}$, the count of specific integer solutions to the system of linear equations $A\mathbf{x} = \mathbf{b}$ with the entries of $\mathbf{x}$ in $[n]_p$ follows a (conveniently rescaled) normal limiting distribution. This applies among others to the number of solutions with every variable having a different value, as well as to a broader class of so-called non-trivial solutions in homogeneous strictly balanced systems. Our proof relies on the delicate linear algebraic study both of the subjacent matrices and the corresponding ranks of certain submatrices, together with the application of the method of moments in probability theory.

We provide the first solution to the problem of counting rooted 3-connected bipartite planar maps. Our starting point is the enumeration of bicoloured planar maps according to the number of edges and monochromatic edges, following Bernardi and Bousquet-M\'elou [J. Comb. Theory Ser. B, 101 (2011), 315-377]. The decomposition of a map into 2- and 3-connected components allows us to obtain the generating functions of 2-and 3-connected bicoloured maps. Setting to zero the variable marking monochromatic edges we obtain the generating function of 3-connected bipartite maps, which is algebraic of degree 26. We deduce from it an asymptotic estimate for the number of 3-connected bipartite planar maps of the form $t \cdot n^{-5/2} \gamma^n$, where $\gamma=\rho^{-1} \approx 2.40958$ and $\rho \approx 0.41501$ is an algebraic number of degree 10., Comment: 15 pages

A well-known conjecture by Lovasz and Plummer from the 1970s asserting that a bridgeless cubic graph has exponentially many perfect matchings was solved in the affirmative by Esperet et al. (Adv. Math. 2011). On the other hand, Chudnovsky and Seymour (Combinatorica 2012) proved the conjecture for the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with n vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically \(c\gamma ^n\), where \(c>0\) and \(\gamma \sim 1.14196\) is an explicit algebraic number. We also compute the expected number of perfect matchings in (non necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations. (Supported by the Ministerio de Economia y Competitividad grant MTM2017-82166-P, and by the Special Research Program F50 Algorithmic and Enumerative Combinatorics of the Austrian Science Fund.).

A set of integers S ⊂ N is an α–strong Sidon set if the pairwise sums of its elements are far apart by a certain measure depending on α, more specifically if | ( x + w ) − ( y + z ) | ≥ max ⁡ { x α , y α , z α , w α } for every x , y , z , w ∈ S satisfying max ⁡ { x , w } ≠ max ⁡ { y , z } . We obtain a new lower bound for the growth of α–strong infinite Sidon sets when 0 ≤ α 1 . We also further extend that notion in a natural way by obtaining the first non-trivial bound for α–strong infinite B h sets. In both cases, we study the implications of these bounds for the density of, respectively, the largest Sidon or B h set contained in a random infinite subset of N . Our theorems improve on previous results by Kohayakawa, Lee, Moreira and Rodl.

The goal of this paper is to obtain quantitative results on the number and on the size of maximal independent sets and maximal matchings in several block-stable graph classes that satisfy a proper sub-criticality condition. In particular we cover trees, cacti graphs and series-parallel graphs. The proof methods are based on a generating function approach and a proper singularity analysis of solutions of implicit systems of functional equations in several variables. As a byproduct, this method extends previous results of Meir and Moon for trees [Meir, Moon: On maximal independent sets of nodes in trees, Journal of Graph Theory 1988]., Comment: 32 pages, 7 figures

Let $k\geq 2$ be a positive integer. We study concentration results for the ordered representation functions $r^{\leq}_k(A,n) = \# \big\{ (a_1 \leq \dots \leq a_k) \in A^k : a_1+\dots+a_k = n \big\}$ and $r^{ 0$ and $\star \in \{\leq,0$. These results extend two theorems for the non-ordered representation function proved by Erd\H{o}s and Fuchs in the case of $k=2$ (J. of the London Math. Society 1956)., Comment: 15 pages

Let L be subset of { 3 , 4 , … } and let X n , M ( L ) be the number of cycles belonging to unicyclic components whose length is in L in the random graph G ( n , M ) . We find the limiting distribution of X n , M ( L ) in the subcritical regime M = c n with c 1 / 2 and the critical regime M = n 2 ( 1 + μ n − 1 / 3 ) with μ = O ( 1 ) . Depending on the regime and a condition involving the series ∑ l ∈ L z l / ( 2 l ) , we obtain in the limit either a Poisson or a normal distribution as n → ∞ .