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:Blanca; Antonio, Sinclair, Alistair, Zhang, Xusheng Pages: 924 - 975 Abstract: The random-cluster model is a unifying framework for studying random graphs, spin systems and electrical networks that plays a fundamental role in designing efficient Markov Chain Monte Carlo (MCMC) sampling algorithms for the classical ferromagnetic Ising and Potts models. In this paper, we study a natural non-local Markov chain known as the Chayes–Machta (CM) dynamics for the mean-field case of the random-cluster model, where the underlying graph is the complete graph on n vertices. The random-cluster model is parametrised by an edge probability p and a cluster weight q. Our focus is on the critical regime: and , where is the threshold corresponding to the order–disorder phase transition of the model. We show that the mixing time of the CM dynamics is in this parameter regime, which reveals that the dynamics does not undergo an exponential slowdown at criticality, a surprising fact that had been predicted (but not proved) by statistical physicists. This also provides a nearly optimal bound (up to the factor) for the mixing time of the mean-field CM dynamics in the only regime of parameters where no non-trivial bound was previously known. Our proof consists of a multi-phased coupling argument that combines several key ingredients, including a new local limit theorem, a precise bound on the maximum of symmetric random walks with varying step sizes and tailored estimates for critical random graphs. In addition, we derive an improved comparison inequality between the mixing time of the CM dynamics and that of the local Glauber dynamics on general graphs; this results in better mixing time bounds for the local dynamics in the mean-field setting. PubDate: 2022-05-11 DOI: 10.1017/S0963548322000037

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:Illingworth; Freddie Pages: 976 - 1009 Abstract: The classical Andrásfai-Erdős-Sós theorem considers the chromatic number of -free graphs with large minimum degree, and in the case, says that any n-vertex triangle-free graph with minimum degree greater than is bipartite. This began the study of the chromatic profile of triangle-free graphs: for each k, what minimum degree guarantees that a triangle-free graph is k-colourable? The chromatic profile has been extensively studied and was finally determined by Brandt and Thomassé. Triangle-free graphs are exactly those in which each neighbourhood is one-colourable. As a natural variant, Luczak and Thomassé introduced the notion of a locally bipartite graph in which each neighbourhood is 2-colourable. Here we study the chromatic profile of the family of graphs in which every neighbourhood is b-colourable (locally b-partite graphs) as well as the family where the common neighbourhood of every a-clique is b-colourable. Our results include the chromatic thresholds of these families (extending a result of Allen, Böttcher, Griffiths, Kohayakawa and Morris) as well as showing that every n-vertex locally b-partite graph with minimum degree greater than is -colourable. Understanding these locally colourable graphs is crucial for extending the Andrásfai-Erdős-Sós theorem to non-complete graphs, which we develop elsewhere. PubDate: 2022-05-10 DOI: 10.1017/S0963548322000050

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:Alon; Noga, Nachmias, Asaf, Shalev, Matan Pages: 1010 - 1030 Abstract: We show that the diameter of a uniformly drawn spanning tree of a simple connected graph on n vertices with minimal degree linear in n is typically of order . A byproduct of our proof, which is of independent interest, is that on such graphs the Cheeger constant and the spectral gap are comparable. PubDate: 2022-05-13 DOI: 10.1017/S0963548322000062

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:Ergemlidze; Beka, Molla, Theodore Pages: 1031 - 1047 Abstract: For a subgraph of the blow-up of a graph , we let be the smallest minimum degree over all of the bipartite subgraphs of induced by pairs of parts that correspond to edges of . Johansson proved that if is a spanning subgraph of the blow-up of with parts of size and , then contains vertex disjoint triangles, and presented the following conjecture of Häggkvist. If is a spanning subgraph of the blow-up of with parts of size PubDate: 2022-05-30 DOI: 10.1017/S0963548322000086

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:Eldan; Ronen, Mikulincer, Dan, Pieters, Hester Pages: 1048 - 1069 Abstract: We make the first steps towards generalising the theory of stochastic block models, in the sparse regime, towards a model where the discrete community structure is replaced by an underlying geometry. We consider a geometric random graph over a homogeneous metric space where the probability of two vertices to be connected is an arbitrary function of the distance. We give sufficient conditions under which the locations can be recovered (up to an isomorphism of the space) in the sparse regime. Moreover, we define a geometric counterpart of the model of flow of information on trees, due to Mossel and Peres, in which one considers a branching random walk on a sphere and the goal is to recover the location of the root based on the locations of leaves. We give some sufficient conditions for percolation and for non-percolation of information in this model. PubDate: 2022-05-31 DOI: 10.1017/S0963548322000098

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:Steiner; Raphael Pages: 1070 - 1075 Abstract: Hadwiger’s conjecture asserts that every graph without a -minor is -colourable. It is known that the exact version of Hadwiger’s conjecture does not extend to list colouring, but it has been conjectured by Kawarabayashi and Mohar (2007) that there exists a constant such that every graph with no -minor has list chromatic number at most . More specifically, they also conjectured that this holds for .Refuting the latter conjecture, we show that the maximum list chromatic number of graphs with no -minor is at least , and hence in the above conjecture is necessary. This improves the previous best lower bound by Barát, Joret and Wood (2011), who proved that . Our lower-bound examples are obtained via the probabilistic method. PubDate: 2022-05-30 DOI: 10.1017/S0963548322000116

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:Liu; Xizhi Pages: 1076 - 1091 Abstract: A hypergraph is non-trivial intersecting if every pair of edges in it have a nonempty intersection, but no vertex is contained in all edges of . Mubayi and Verstraëte showed that for every and every -graph on vertices without a non-trivial intersecting subgraph of size contains at most edges. They conjectured that the same conclusion holds for all and sufficiently large . We confirm their conjecture by proving a stronger statement.They also conjectured that for and sufficiently large the maximum size of a PubDate: 2022-06-09 DOI: 10.1017/S096354832200013X

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:Lo; Allan, Treglown, Andrew, Zhao, Yi Pages: 1092 - 1101 Abstract: In 1975 Bollobás, Erdős, and Szemerédi asked the following question: given positive integers with , what is the largest minimum degree among all -partite graphs with parts of size and which do not contain a copy of ? The case has attracted a lot of attention and was fully resolved by Haxell and Szabó, and Szabó and Tardos in 2006. In this article, we investigate the case of the problem, which has remained dormant for over 40 years. We resolve the problem exactly in the case when , and up to an additive constant for many other cases, including when . Our approach utilizes a connection to the related problem of determining the maximum of the minimum degrees among the family of balanced -partite PubDate: 2022-06-13 DOI: 10.1017/S0963548322000141