ﻻ يوجد ملخص باللغة العربية
This paper is concerned with symmetric $1$-dependent colorings of the $d$-ray star graph $mathscr{S}^d$ for each $d ge 2$. We compute the critical point of the $1$-dependent hard-core processes on $mathscr{S}^d$, which gives a lower bound for the number of colors needed for a $1$-dependent coloring of $mathscr{S}^d$. We provide an explicit construction of a $1$-dependent $q$-coloring for any $q ge 5$ of the infinite subgraph $mathscr{S}^3_{(1,1,infty)}$, which is symmetric in the colors and whose restriction to any copy of $mathbb{Z}$ is some symmetric $1$-dependent $q$-coloring of $mathbb{Z}$. We also prove that there is no such coloring of $mathscr{S}^3_{(1,1,infty)}$ with $q = 4$ colors. A list of open problems are presented.
In a recent paper by the same authors, we constructed a stationary 1-dependent 4-coloring of the integers that is invariant under permutations of the colors. This was the first stationary k-dependent q-coloring for any k and q. When the analogous con
We study two weighted graph coloring problems, in which one assigns $q$ colors to the vertices of a graph such that adjacent vertices have different colors, with a vertex weighting $w$ that either disfavors or favors a given color. We exhibit a weigh
Very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), due to the presence of low-degree dependencies such as isolated vertices and pairs of degree-1 vertices with the same neighbourhood. We prove that th
A wide array of random graph models have been postulated to understand properties of observed networks. Typically these models have a parameter $t$ and a critical time $t_c$ when a giant component emerges. It is conjectured that for a large class of
We study random walks on the giant component of the ErdH{o}s-Renyi random graph ${cal G}(n,p)$ where $p=lambda/n$ for $lambda>1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Ko