Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinitely dependent coloring
78
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We prove that proper coloring distinguishes between block-factors and finitely dependent stationary processes. A stochastic process is finitely dependent if variables at sufficiently well-separated locations are independent; it is a block-factor if it can be expressed as an equivariant finite-range function of independent variables. The problem of finding non-block-factor finitely dependent processes dates back to 1965. The first published example appeared in 1993, and we provide arguably the first natural examples. More precisely, Schramm proved in 2008 that no stationary 1-dependent 3-coloring of the integers exists, and conjectured that no stationary k-dependent q-coloring exists for any k and q. We disprove this by constructing a 1-dependent 4-coloring and a 2-dependent 3-coloring, thus resolving the question for all k and q. Our construction is canonical and natural, yet very different from all previous schemes. In its pure form it yields precisely the two finitely dependent colorings mentioned above, and no others. The processes provide unexpected connections between extremal cases of the Lovasz local lemma and descent and peak sets of random permutations. Neither coloring can be expressed as a block-factor, nor as a function of a finite-state Markov chain; indeed, no stationary finitely dependent coloring can be so expressed. We deduce extensions involving d dimensions and shifts of finite type; in fact, any non-degenerate shift of finite type also distinguishes between block-factors and finitely dependent processes.
rate research
Read More
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 construction is carried out for q>4 colors, the resulting process is not k-dependent for any k. We construct here a process that is symmetric in the colors and 1-dependent for every q>=4. The construction uses a recursion involving Chebyshev polynomials evaluated at $sqrt{q}/2$.
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.
We compute the best constant in the Khintchine inequality under assumption that the sum of Rademacher random variables is zero.
We propose a numerical method for studying the cogrowth of finitely presented groups. To validate our numerical results we compare them against the corresponding data from groups whose cogrowth series are known exactly. Further, we add to the set of such groups by finding the cogrowth series for Baumslag-Solitar groups $mathrm{BS}(N,N) = < a,b | a^N b = b a^N >$ and prove that their cogrowth rates are algebraic numbers.
In 1960, Asplund and Grunbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an $O(omega^2)$-coloring, where $omega$ is the maximum size of a clique. We present the first asymptotic improvement over this six-decade-old bound, proving that every such graph is $O(omegalogomega)$-colorable and presenting a polynomial-time algorithm that finds such a coloring. This improvement leads to a polynomial-time $O(loglog n)$-approximation algorithm for the maximum weight independent set problem in axis-parallel rectangles, which improves on the previous approximation ratio of $O(frac{log n}{loglog n})$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
