Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Berzunza Ojeda; Gabriel, Janson, Svante Pages: 368 - 410 Abstract: It is well known that the height profile of a critical conditioned Galton–Watson tree with finite offspring variance converges, after a suitable normalisation, to the local time of a standard Brownian excursion. In this work, we study the distance profile, defined as the profile of all distances between pairs of vertices. We show that after a proper rescaling the distance profile converges to a continuous random function that can be described as the density of distances between random points in the Brownian continuum random tree. We show that this limiting function a.s. is Hölder continuous of any order , and that it is a.e. differentiable. We note that it cannot be differentiable at 0, but leave as open questions whether it is Lipschitz, and whether it is continuously differentiable on the half-line . The distance profile is naturally defined also for unrooted trees contrary to the height profile that is designed for rooted trees. This is used in our proof, and we prove the corresponding convergence result for the distance profile of random unrooted simply generated trees. As a minor purpose of the present work, we also formalize the notion of unrooted simply generated trees and include some simple results relating them to rooted simply generated trees, which might be of independent interest. PubDate: 2021-08-18 DOI: 10.1017/S0963548321000304

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Coulson; Matthew Pages: 411 - 429 Abstract: We consider the component structure of the random digraph D(n,p) inside the critical window . We show that the largest component has size of order in this range. In particular we give explicit bounds on the tail probabilities of . PubDate: 2021-10-08 DOI: 10.1017/S096354832100033X

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Heydenreich; Markus, Matzke, Kilian Pages: 430 - 454 Abstract: We expand the critical point for site percolation on the d-dimensional hypercubic lattice in terms of inverse powers of 2d, and we obtain the first three terms rigorously. This is achieved using the lace expansion. PubDate: 2021-09-28 DOI: 10.1017/S0963548321000365

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Ferber; Asaf, Jain, Vishesh, Zhao, Yufei Pages: 455 - 477 Abstract: Many problems in combinatorial linear algebra require upper bounds on the number of solutions to an underdetermined system of linear equations , where the coordinates of the vector x are restricted to take values in some small subset (e.g. ) of the underlying field. The classical ways of bounding this quantity are to use either a rank bound observation due to Odlyzko or a vector anti-concentration inequality due to Halász. The former gives a stronger conclusion except when the number of equations is significantly smaller than the number of variables; even in such situations, the hypotheses of Halász’s inequality are quite hard to verify in practice. In this paper, using a novel approach to the anti-concentration problem for vector sums, we obtain new Halász-type inequalities that beat the Odlyzko bound even in settings where the number of equations is comparable to the number of variables. In addition to being stronger, our inequalities have hypotheses that are considerably easier to verify. We present two applications of our inequalities to combinatorial (random) matrix theory: (i) we obtain the first non-trivial upper bound on the number of Hadamard matrices and (ii) we improve a recent bound of Deneanu and Vu on the probability of normality of a random matrix. PubDate: 2021-09-10 DOI: 10.1017/S0963548321000377

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Freschi; Andrea, Hyde, Joseph, Treglown, Andrew Pages: 478 - 488 Abstract: Motivated by analogous questions in the setting of Steiner triple systems and Latin squares, Nenadov, Sudakov and Wagner [Completion and deficiency problems, Journal of Combinatorial Theory Series B, 2020] recently introduced the notion of graph deficiency. Given a global spanning property and a graph , the deficiency of the graph with respect to the property is the smallest non-negative integer t such that the join has property . In particular, Nenadov, Sudakov and Wagner raised the question of determining how many edges an n-vertex graph needs to ensure contains a -factor (for any fixed ). In this paper, we resolve their problem fully. We also give an analogous result that forces to contain any fixed bipartite PubDate: 2021-09-27 DOI: 10.1017/S0963548321000389

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Axenovich; Maria, Girão, António, Snyder, Richard, Weber, Lea Pages: 489 - 506 Abstract: Kostochka and Thomason independently showed that any graph with average degree contains a minor. In particular, any graph with chromatic number contains a minor, a partial result towards Hadwiger’s famous conjecture. In this paper, we investigate analogues of these results in the directed setting. There are several ways to define a minor in a digraph. One natural way is as follows. A strongminor is a digraph whose vertex set is partitioned into r parts such that each part induces a strongly connected subdigraph, and there is at least one edge in each direction between any two distinct parts. We investigate bounds on the dichromatic number and minimum out-degree of a digraph that force the existence of strong minors as subdigraphs. In particular, we show that any tournament with dichromatic number at least 2r contains a strong minor, and any tournament with minimum out-degree also contains a strong minor. The latter result is tight up to the implied constant and may be viewed as a strong-minor analogue to the classical result of Kostochka and Thomason. Lastly, we show that there is no function such that any digraph with minimum out-degree at least f(r) contains a strong minor, but such a function exists when considering d... PubDate: 2021-09-24 DOI: 10.1017/S0963548321000390

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Authors:Avohou; Remi C., Ben Geloun, Joseph, Hounkonnou, Mahouton N. Pages: 507 - 549 Abstract: The Bollobás–Riordan (BR) polynomial [(2002), Math. Ann.323 81] is a universal polynomial invariant for ribbon graphs. We find an extension of this polynomial for a particular family of combinatorial objects, called rank 3 weakly coloured stranded graphs. Stranded graphs arise in the study of tensor models for quantum gravity in physics, and generalize graphs and ribbon graphs. We present a seven-variable polynomial invariant of these graphs, which obeys a contraction/deletion recursion relation similar to that of the Tutte and BR polynamials. However, it is defined on a much broader class of objects, and furthermore captures properties that are not encoded by the Tutte or BR polynomials. PubDate: 2021-10-25 DOI: 10.1017/S096354832100050X