|
Combinatorics, Probability and Computing
Journal Prestige (SJR): 0.839  Citation Impact (citeScore): 1 Number of Followers: 4  Hybrid journal (It can contain Open Access articles)ISSN (Print) 0963-5483 - ISSN (Online) 1469-2163 Published by Cambridge University Press  [353 journals]
|
- The distance profile of rooted and unrooted simply generated trees
-
Free pre-print version: Loading...
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
-
- The critical window in random digraphs
-
Free pre-print version: Loading...
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
-
- Expansion for the critical point of site percolation: the first three
terms-
Free pre-print version: Loading...
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
-
- On the number of Hadamard matrices via anti-concentration
-
Free pre-print version: Loading...
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
-
- On deficiency problems for graphs
-
Free pre-print version: Loading...
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
-
- Strong complete minors in digraphs
-
Free pre-print version: Loading...
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 strong
minor 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
-
- Extending the Tutte and Bollobás–Riordan polynomials to rank 3 weakly
coloured stranded graphs-
Free pre-print version: Loading...
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
-
