Lucas Aragão,Maurício Collares,João Pedro Marciano et al.
Lucas Aragão et al.
The set-coloring Ramsey number Rr,s(k) is defined to be the minimum n such that if each edge of the complete graph Kn is assigned a set of s colors from {1,…,r}, then one of the colors contains a monochromatic clique of size k. The ca...
Weiming Feng,Heng Guo,Yitong Yin
Weiming Feng
We introduce a new perfect sampling technique that can be applied to general Gibbs distributions and runs in linear time if the correlation decays faster than the neighborhood growth. In particular, in graphs with subexponential neighborhoo...
A Nicholas Day,Victor Falgas-Ravry,Robert Hancock
A Nicholas Day
A probability measure μ on the subsets of the edge set of a graph G is a 1-independent probability measure (1-ipm) on G if events determined by edge sets that are at graph distance at least 1 apart in G are independent. Given a 1-ipm &...
Ewan Davies,Rémi de Joannis de Verclos,Ross J Kang et al.
Ewan Davies et al.
We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow-up work of Bernshteyn) on the (list) chromatic number of triangle-free graphs. In both our results, we permit the amount of color made ava...
Michael Drmota,Emma Yu Jin,Benedikt Stufler
Michael Drmota
For any set Ω of non-negative integers such that { 0 , 1 } ⊊ Ω , we consider a random Ω-k-tree G n,k that is uniformly selected from all connected k-trees of (n + k) vertices such that the number of (k + 1)-cliques that contain...
Francesco Caravenna,Alessandro Garavaglia,Remco van der Hofstad
Francesco Caravenna
It is well known that many random graphs with infinite variance degrees are ultra-small. More precisely, for configuration models and preferential attachment models where the proportion of vertices of degree at least k is approximately k -(...
Sayan Mukherjee,John Steenbergen
Sayan Mukherjee
In this paper, we introduce a class of random walks with absorbing states on simplicial complexes. Given a simplicial complex of dimension d, a random walk with an absorbing state is defined which relates to the spectrum of the k-dimensiona...
Victor Bapst,Amin Coja-Oghlan
Victor Bapst
A wide class of problems in combinatorics, computer science and physics can be described along the following lines. There are a large number of variables ranging over a finite domain that interact through constraints that each bind a few va...