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: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

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: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

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: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

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: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

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: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

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: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

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: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

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: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