|
Combinatorics, Probability and Computing
Journal Prestige (SJR): 0.839  Citation Impact (citeScore): 1 Number of Followers: 5  Hybrid journal (It can contain Open Access articles)ISSN (Print) 0963-5483 - ISSN (Online) 1469-2163 Published by Cambridge University Press  [353 journals]
|
- Unimodular random one-ended planar graphs are sofic
-
Free pre-print version: Loading...
Authors: Timár; Ádám
Pages: 851 - 858
Abstract: We prove that if a unimodular random graph is almost surely planar and has finite expected degree, then it has a combinatorial embedding into the plane which is also unimodular. This implies the claim in the title immediately by a theorem of Angel, Hutchcroft, Nachmias and Ray [2]. Our unimodular embedding also implies that all the dichotomy results of [2] about unimodular maps extend in the one-ended case to unimodular random planar graphs.
PubDate: 2023-06-09
DOI: 10.1017/S0963548323000159
-
- Archaeology of random recursive dags and Cooper-Frieze random networks
-
Free pre-print version: Loading...
Authors: Briend; Simon, Calvillo, Francisco, Lugosi, Gábor
Pages: 859 - 873
Abstract: We study the problem of finding the root vertex in large growing networks. We prove that it is possible to construct confidence sets of size independent of the number of vertices in the network that contain the root vertex with high probability in various models of random networks. The models include uniform random recursive dags and uniform Cooper-Frieze random graphs.
PubDate: 2023-06-13
DOI: 10.1017/S0963548323000184
-
- On the size-Ramsey number of grids
-
Free pre-print version: Loading...
Authors: Conlon; David, Nenadov, Rajko, Trujić, Miloš
Pages: 874 - 880
Abstract: We show that the size-Ramsey number of the
grid graph is 
, improving a previous bound of 
by Clemens, Miralaei, Reding, Schacht, and Taraz.
PubDate: 2023-06-26
DOI: 10.1017/S0963548323000147
-
- The codegree Turán density of tight cycles minus one edge
-
Free pre-print version: Loading...
Authors: Piga; Simón, Sales, Marcelo, Schülke, Bjarne
Pages: 881 - 884
Abstract: Given
and an integer 
, we prove that every sufficiently large 
-uniform hypergraph 
on 
vertices in which every two vertices are contained in at least 
edges contains a copy of 
, a tight cycle on 
vertices minus one edge. This improves a previous result by Balogh, Clemen, and Lidický.
PubDate: 2023-07-05
DOI: 10.1017/S0963548323000196
-
- Polarised random $k$-SAT
-
Free pre-print version: Loading...
Authors: Danielsson; Joel Larsson, Markström, Klas
Pages: 885 - 899
Abstract: In this paper we study a variation of the random
-SAT problem, called polarised random 
-SAT, which contains both the classical random 
-SAT model and the random version of monotone 
-SAT another well-known NP-complete version of SAT. In this model there is a polarisation parameter 
, and in half of the clauses each variable occurs negated with probability 
and pure otherwise, while in the other half the probabilities are interchanged. For 
we get the classical random 
-SAT model, and at the other extreme we have the fully polarised model where 
, or 1. Here there are only two types of clauses: clauses where all 
variables occur pure, and clauses where all 
variables occur negated. That is, for 
, and
PubDate: 2023-07-20
DOI: 10.1017/S0963548323000226
-
- On the maximum number of edges in $k$-critical graphs
-
Free pre-print version: Loading...
Authors: Luo; Cong, Ma, Jie, Yang, Tianchi
Pages: 900 - 911
Abstract: A graph is called
-critical if its chromatic number is 
but every proper subgraph has chromatic number less than 
. An old and important problem in graph theory asks to determine the maximum number of edges in an 
-vertex 
-critical graph. This is widely open for every integer 
. Using a structural characterisation of Greenwell and Lovász and an extremal result of Simonovits, Stiebitz proved in 1987 that for 
and sufficiently large 
, this maximum number is less than the number of edges in the 
-vertex balanced complete 
-partite graph. In this paper, we obtain the first improvement in the above result in the past 35 years. Our proofs combine arguments from extremal graph theory as well as some structural analysis. A key lemma we use indicates a partial structure in dense 
-critical graphs, which may be of independent interest.
PubDate: 2023-07-24
DOI: 10.1017/S0963548323000238
-
- On the exponential growth rates of lattice animals and interfaces
-
Free pre-print version: Loading...
Authors: Georgakopoulos; Agelos, Panagiotis, Christoforos
Pages: 912 - 955
Abstract: We introduce a formula for translating any upper bound on the percolation threshold of a lattice
into a lower bound on the exponential growth rate of lattice animals 
and vice versa. We exploit this in both directions. We obtain the rigorous lower bound 
for 3-dimensional site percolation. We also improve on the best known asymptotic bounds on 
as 
. Our formula remains valid if instead of lattice animals we enumerate certain subspecies called interfaces. Enumerating interfaces leads to functional duality formulas that are tightly connected to percolation and are not valid for lattice animals, as well as to strict inequalities for the percolation threshold.Incidentally, we prove that the rate of the exponential decay of the cluster size distribution of Bernoulli percolation is a continuous function of 
.
PubDate: 2023-07-31
DOI: 10.1017/S0963548323000214
-
- Limiting empirical spectral distribution for the non-backtracking matrix
of an Erdős-Rényi random graph-
Free pre-print version: Loading...
Authors: Wang; Ke, Wood, Philip Matchett
Pages: 956 - 973
Abstract: In this note, we give a precise description of the limiting empirical spectral distribution for the non-backtracking matrices for an Erdős-Rényi graph
assuming 
tends to infinity. We show that derandomizing part of the non-backtracking random matrix simplifies the spectrum considerably, and then, we use Tao and Vu’s replacement principle and the Bauer-Fike theorem to show that the partly derandomized spectrum is, in fact, very close to the original spectrum.
PubDate: 2023-07-31
DOI: 10.1017/S096354832300024X
-
