Let $\Omega_q$ denote the set of proper $[q]$colorings of the random graph $G_{n,m}, m=dn/2$ and let $H_q$ be the graph with vertex set $\Omega_q$ and an edge $\set{\s,\t}$ where $\s,\t$ are mappings $[n]\to[q]$ iff $h(\s,\t)=1$. Here $h(\s,\t)$ is the Hamming distance $\set{v\in [n]:\s(v)\neq\t(v)}$. We show that w.h.p. $H_q$ contains a single giant component containing almost all colorings in $\Omega_q$ if $d$ is sufficiently large and $q\geq \frac{cd}{\log d}$ for a constant $c>3/2$.
more »
« less
Constraining the Clustering Transition for Colorings of Sparse Random Graphs
Let Ωq denote the set of proper [q]colorings of the random graph Gn,m,m=dn/2 and let Hq be the graph with vertex set Ωq and an edge {σ,τ} where σ,τ are mappings [n]→[q] iff h(σ,τ)=1. Here h(σ,τ) is the Hamming distance {v∈[n]:σ(v)≠τ(v)}. We show that w.h.p. Hq contains a single giant component containing almost all colorings in Ωq if d is sufficiently large and q≥cdlogd for a constant c>3/2.
more »
« less
 Award ID(s):
 1700365
 NSFPAR ID:
 10106974
 Date Published:
 Journal Name:
 The Electronic journal of combinatorics
 Volume:
 25
 Issue:
 1
 ISSN:
 10778926
 Page Range / eLocation ID:
 P1.72
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Let Ω_{q}=Ω_{q}(
H ) denote the set of proper [q ]‐colorings of the hypergraphH . Let Γ_{q}be the graph with vertex set Ω_{q}where two coloringsσ ,τ are adjacent iff the corresponding colorings differ in exactly one vertex. We show that ifH =H _{n,m;k},k ≥ 2, the randomk ‐uniform hypergraph withV =[n ] andm =dn /k hyperedges then w.h.p. Γ_{q}is connected ifd is sufficiently large and. This is optimal up to the first order in d . Furthermore, with a few more colors, we find that the diameter of Γ_{q}isO (n ) w.h.p., where the hidden constant depends ond . So, with this choice ofd ,q , the natural Glauber dynamics Markov Chain on Ω_{q}is ergodic w.h.p. 
null (Ed.)Abstract For positive integers n and d > 0, let $G(\mathbb {Q}^n,\; d)$ denote the graph whose vertices are the set of rational points $\mathbb {Q}^n$ , with $u,v \in \mathbb {Q}^n$ being adjacent if and only if the Euclidean distance between u and v is equal to d . Such a graph is deemed “nontrivial” if d is actually realized as a distance between points of $\mathbb {Q}^n$ . In this paper, we show that a space $\mathbb {Q}^n$ has the property that all pairs of nontrivial distance graphs $G(\mathbb {Q}^n,\; d_1)$ and $G(\mathbb {Q}^n,\; d_2)$ are isomorphic if and only if n is equal to 1, 2, or a multiple of 4. Along the way, we make a number of observations concerning the clique number of $G(\mathbb {Q}^n,\; d)$ .more » « less

Let $N=\binom{n}{2}$ and $s\geq 2$. Let $e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$ be $s$ independent permutations of the edges $E(K_n)$ of the complete graph $K_n$. A MultiTree is a set $I\subseteq [N]$ such that the edge sets $E_{I,j}$ induce spanning trees for $j=1,2,\ldots,s$. In this paper we study the following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a hitting time result for $s=2$ and an $O(n\log n)$ bound for $s\geq 3$.more » « less

Radio 2colorings of graphs are a generalization of vertex colorings motivated by the problem of assigning frequency channels in radio networks. In a radio 2coloring of a graph, vertices are assigned integer colors so that the color of two vertices u and v differ by at least 2 if u and v are neighbors, and by at least 1 if u and v have a common neighbor. Our work improves the bestknown bounds for optimal radio 2colorings of small hypercube graphs, a combinatorial problem that has received significant attention in the past. We do so by using automated reasoning techniques such as symmetry breaking and Cube and Conquer, obtaining that for n = 7 and n = 8, the codingtheory upper bounds of Whittlesey et al. (1995) are not tight. Moreover, we prove the answer for n = 7 to be either 12 or 13, thus making a substantial step towards answering an open problem by Knuth (2015). Finally, we include several combinatorial observations that might be useful for further progress, while also arguing that fully determining the answer for n = 7 will require new techniques.more » « less