JournalTOCs

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

[386 journals]

Edge-statistics on large graphs
- Authors: Noga Alon; Dan Hefetz, Michael Krivelevich, Mykhaylo Tyomkyn
  Pages: 163 - 189
  Abstract: The inducibility of a graph H measures the maximum number of induced copies of H a large graph G can have. Generalizing this notion, we study how many induced subgraphs of fixed order k and size ℓ a large graph G on n vertices can have. Clearly, this number is $\left( {\matrix{n \cr k}}\right)$ for every n, k and $\ell \in \left\{ {0,\left( {\matrix{k \cr 2}} \right)}\right\}$ . We conjecture that for every n, k and $0 \lt \ell \lt \left( {\matrix{k \cr 2}}\right)$ this number is at most $ (1/e + {o_k}(1)) {\left( {\matrix{n \cr k}} \right)}$ . If true, this would be tight for ℓ ∈ {1, k − 1}.In support of our ‘Edge-statistics Conjecture’, we prove that the corresponding density is bounded away from 1 by an absolute constant. Furthermore, for various ranges of the values of ℓ we establish stronger bounds. In particular, we prove that for ‘almost all’ pairs (k, ℓ) only a polynomially small fraction of the k-subsets of V(G) have exactly ℓ edges, and prove an upper bound of $ (1/2 + {o_k}(1)){\left( {\matrix{n \cr k}}\right)}$ for ℓ = 1.Our proof methods involve probabilistic tools, such as anti-concentration results relying on fourth moment estimates and Brun’s sieve, as well as graph-theoretic and combinatorial arguments such as Zykov’s symmetrization, Sperner’s theorem and various counting techniques.
  PubDate: 2020-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548319000294
  Issue No: Vol. 29, No. 2 (2020)
The string of diamonds is nearly tight for rumour spreading
- Authors: Omer Angel; Abbas Mehrabian, Yuval Peres
  Pages: 190 - 199
  Abstract: For a rumour spreading protocol, the spread time is defined as the first time everyone learns the rumour. We compare the synchronous push&pull rumour spreading protocol with its asynchronous variant, and show that for any n-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by $O({n^{1/3}}{\log ^{2/3}}n)$ . This improves the $O(\sqrt n)$ upper bound of Giakkoupis, Nazari and Woelfel (2016). Our bound is tight up to a factor of O(log n), as illustrated by the string of diamonds graph. We also show that if, for a pair α, β of real numbers, there exist infinitely many graphs for which the two spread times are nα and nβ in expectation, then $0 \le \alpha \le 1$ and $\alpha \le \beta \le {1 \over 3} + {2 \over 3} \alpha $ ; and we show each such pair α, β is achievable.
  PubDate: 2020-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548319000385
  Issue No: Vol. 29, No. 2 (2020)
FKN theorem for the multislice, with applications
- Authors: Yuval Filmus
  Pages: 200 - 212
  Abstract: The Friedgut–Kalai–Naor (FKN) theorem states that if ƒ is a Boolean function on the Boolean cube which is close to degree one, then ƒ is close to a dictator, a function depending on a single coordinate. The author has extended the theorem to the slice, the subset of the Boolean cube consisting of all vectors with fixed Hamming weight. We extend the theorem further, to the multislice, a multicoloured version of the slice.As an application, we prove a stability version of the edge-isoperimetric inequality for settings of parameters in which the optimal set is a dictator.
  PubDate: 2020-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548319000361
  Issue No: Vol. 29, No. 2 (2020)
Sharp concentration of the equitable chromatic number of dense random
graphs
- Authors: Annika Heckel
  Pages: 213 - 233
  Abstract: An equitable colouring of a graph G is a vertex colouring where no two adjacent vertices are coloured the same and, additionally, the colour class sizes differ by at most 1. The equitable chromatic number χ=(G) is the minimum number of colours required for this. We study the equitable chromatic number of the dense random graph ${\mathcal{G}(n,m)}$ where $m = \left\lfloor {p\left( \matrix{ n \cr 2 \cr} \right)} \right\rfloor $ and 0 < p < 0.86 is constant. It is a well-known question of Bollobás [3] whether for p = 1/2 there is a function f(n) → ∞ such that, for any sequence of intervals of length f(n), the normal chromatic number of ${\mathcal{G}(n,m)}$ lies outside the intervals with probability at least 1/2 if n is large enough. Bollobás proposes that this is likely to hold for f(n) = log n. We show that for the equitable chromatic number, the answer to the analogous question is negative. In fact, there is a subsequence ${({n_j})_j}_{ \in {\mathbb {N}}}$ of the integers where $\chi_=({\mathcal{G}(n_j,m_j)})$ is concentrated on exactly one explicitly known value. This constitutes surprisingly narrow concentration since in this range the equitable chromatic number, like the normal chromatic number, is rather large in absolute value, namely asymptotically equal to n/(2logbn) where b = 1/(1 − p).
  PubDate: 2020-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548319000397
  Issue No: Vol. 29, No. 2 (2020)
On the number of symbols that forces a transversal
- Authors: Peter Keevash; Liana Yepremyan
  Pages: 234 - 240
  Abstract: Akbari and Alipour [1] conjectured that any Latin array of order n with at least n2/2 symbols contains a transversal. For large n, we confirm this conjecture, and moreover, we show that n399/200 symbols suffice.
  PubDate: 2020-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548319000282
  Issue No: Vol. 29, No. 2 (2020)
On the Brownian separable permuton
- Authors: Mickaël Maazoun
  Pages: 241 - 266
  Abstract: The Brownian separable permuton is a random probability measure on the unit square, which was introduced by Bassino, Bouvel, Féray, Gerin and Pierrot (2016) as the scaling limit of the diagram of the uniform separable permutation as size grows to infinity. We show that, almost surely, the permuton is the pushforward of the Lebesgue measure on the graph of a random measure-preserving function associated to a Brownian excursion whose strict local minima are decorated with independent and identically distributed signs. As a consequence, its support is almost surely totally disconnected, has Hausdorff dimension one, and enjoys self-similarity properties inherited from those of the Brownian excursion. The density function of the averaged permuton is computed and a connection with the shuffling of the Brownian continuum random tree is explored.
  PubDate: 2020-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548319000300
  Issue No: Vol. 29, No. 2 (2020)
Surjectivity of near-square random matrices
- Authors: Hoi. H. Nguyen; Elliot Paquette
  Pages: 267 - 292
  Abstract: We show that a nearly square independent and identically distributed random integral matrix is surjective over the integral lattice with very high probability. This answers a question by Koplewitz [6]. Our result extends to sparse matrices as well as to matrices of dependent entries.
  PubDate: 2020-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548319000348
  Issue No: Vol. 29, No. 2 (2020)
Unlabelled Gibbs partitions
- Authors: Benedikt Stufler
  Pages: 293 - 309
  Abstract: We study random composite structures considered up to symmetry that are sampled according to weights on the inner and outer structures. This model may be viewed as an unlabelled version of Gibbs partitions and encompasses multisets of weighted combinatorial objects. We describe a general setting characterized by the formation of a giant component. The collection of small fragments is shown to converge in total variation toward a limit object following a Pólya–Boltzmann distribution.
  PubDate: 2020-03-01T00:00:00.000Z
  DOI: 10.1017/S0963548319000336
  Issue No: Vol. 29, No. 2 (2020)
Counting higher order tangencies for plane curves
- Authors: Joshua Zahl
  Pages: 310 - 317
  Abstract: We prove that n plane algebraic curves determine O(n(k+2)/(k+1)) points of kth order tangency. This generalizes an earlier result of Ellenberg, Solymosi and Zahl on the number of (first order) tangencies determined by n plane algebraic curves.
  PubDate: 2020-03-01T00:00:00.000Z
  DOI: 10.1017/S096354831900035X
  Issue No: Vol. 29, No. 2 (2020)