BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let Γ be a countable group and let G be the Schreier graph of the free part of the Bernoulli shift of Γ (with respect to some finite subset F⊆Γ). We show that the Borel fractional chromatic number of G is equal to 1 over the measurable independence number of G. As a consequence, we asymptotically determine the Borel fractional chromatic number of G when Γ is the free group, answering a question of Meehan.
A conjecture of Alon, Krivelevich, and Sudakov states that, for any graph F, there is a constant cF>0 such that if G is an F-free graph of maximum degree Δ, then χ(G)≤cFΔ/logΔ. Alon, Krivelevich, and Sudakov verified this conjecture for a class of graphs F that includes all bipartite graphs. Moreover, it follows from recent work by Davies, Kang, Pirot, and Sereni that if G is Kt,t-free, then χ(G)≤(t+o(1))Δ/logΔ as Δ→∞. We improve this bound to (1+o(1))Δ/logΔ, making the constant factor independent of t. We further extend our result to the DP-coloring setting (also known as correspondence coloring), introduced by Dvořák and Postle.
This is a draft of an article to appear in the October 2022 issue of the Notices of the AMS. In this survey article we explore a fascinating area called descriptive combinatorics and its recently discovered connections to distributed algorithms -- a fundamental part of computer science that is becoming increasingly important in the modern era of decentralized computation. In the first part of the article we give a brief introduction to some of the central notions and problems of descriptive combinatorics. The second part is devoted to an overview of some of the results concerning the interactions between descriptive combinatorics and distributed algorithms, as well as a few open problems. The article should be accessible to readers with little to no background in either descriptive set theory or computer science.
The probabilistic method is a technique for proving combinatorial existence results by means of showing that a randomly chosen object has the desired properties with positive probability. A particularly powerful probabilistic tool is the Lovász Local Lemma (the LLL for short), which was introduced by Erdős and Lovász in the mid-1970s. Here we develop a version of the LLL that can be used to prove the existence of continuous colorings. We then give several applications in Borel and topological dynamics. * Seward and Tucker-Drob showed that every free Borel action Γ↷X of a countable group Γ admits an equivariant Borel map π:X→Y to a free subshift Y⊂2Γ. We give a new simple proof of this result. * We show that for a countable group Γ, Free(2Γ) is weakly contained, in the sense of Elek, in every free continuous action of Γ on a zero-dimensional Polish space. This fact is analogous to the theorem of Abért and Weiss for probability measure-preserving actions and has a number of consequences in continuous combinatorics. In particular, we deduce that a coloring problem admits a continuous solution on Free(2Γ) if and only if it can be solved on finite subgraphs of the Cayley graph of Γ by an efficient deterministic distributed algorithm (this fact was also proved independently and using different methods by Seward). This establishes a formal correspondence between questions that have been studied independently in continuous combinatorics and in distributed computing.
In this paper we analyze a variant of the pursuit-evasion game on a graph G where the intruder occupies a vertex, is allowed to move to adjacent vertices or remain in place, and is 'invisible' to the searcher, meaning that the searcher operates with no knowledge of the position of the intruder. On each stage, the searcher is allowed to inspect an arbitrary set of k vertices. The minimum k for which the searcher can guarantee the capture of the intruder is called the inspection number of G. We also introduce and study the topological inspection number, a quantity that captures the limiting behavior of the inspection number under subdivisions of G. Our central theorem provides a full classification of graphs with topological inspection number up to 3.
We present a deterministic distributed algorithm in the LOCAL model that finds a proper (Δ+1)-edge-coloring of an n-vertex graph of maximum degree Δ in poly(Δ,logn) rounds. This is the first nontrivial distributed edge-coloring algorithm that uses only Δ+1 colors (matching the bound given by Vizing's theorem). Our approach is inspired by the recent proof of the measurable version of Vizing's theorem due to Grebík and Pikhurko.
Recently, Glasner, Tsankov, Weiss, and Zucker showed that if Γ is an infinite discrete group, then every minimal Γ-flow is disjoint from the Bernoulli shift 2Γ. Their proof is somewhat involved; in particular, it invokes separate arguments for different classes of groups. In this note, we give a short and self-contained proof of their result using purely combinatorial methods applicable to all groups at once. Our proof relies on the Lovász Local Lemma, an important tool in probabilistic combinatorics that has recently found several applications in the study of dynamical systems.
Classical problems in hypergraph coloring theory are to estimate the minimum number of edges, m2(r) (respectively, m2∗(r)), in a non-2-colorable r-uniform (respectively, r-uniform and simple) hypergraph. The best currently known bounds are c⋅r/logr⋅2r⩽m2(r)⩽C⋅r2⋅2randc′⋅r−ε⋅4r⩽m2∗(r)⩽C′⋅r4⋅4r, for any fixed ε>0 and some c, c′, C, C′>0 (where c′ may depend on ε). In this paper we consider the same problems in the context of DP-coloring (also known as correspondence coloring), which is a generalization of list coloring introduced by Dvořák and Postle and related to local conflict coloring studied independently by Fraigniaud, Heinrich, and Kosowski. Let m~2(r) (respectively, m~2∗(r)) denote the minimum number of edges in a non-2-DP-colorable r-uniform (respectively, r-uniform and simple) hypergraph. By definition, m~2(r)⩽m2(r) and m~2∗(r)⩽m2∗(r). While the proof of the bound m2∗(r)=Ω(r−34r) due to Erdős and Lovász also works for m~2∗(r), we show that the trivial lower bound m~2(r)⩾2r−1 is asymptotically tight, i.e., m~2(r)⩽(1+o(1))2r−1. On the other hand, when r⩾2 is even, we prove that the lower bound m~2(r)⩾2r−1 is not sharp, i.e., m~2(r)⩾2r−1+1. Whether this result holds for any odd values of r remains an open problem. Nevertheless, we conjecture that the difference m~2(r)−2r−1 can be arbitrarily large.
In this paper we study hypergraphs definable in an algebraically closed field. Our goal is to show, in the spirit of the so-called transference principles in extremal combinatorics, that if a given algebraic hypergraph is "dense" in a certain sense, then a generic low-dimensional subset of its vertices induces a subhypergraph that is also "dense." (For technical reasons, we only consider low-dimensional subsets that are parameterized by rational functions.) Our proof approach is inspired by the hypergraph containers method, developed by Balogh, Morris, and Samotij and independently by Saxton and Thomason (although adapting this method to the algebraic setting presents some unique challenges that do not occur when working with finite hypergraphs). Along the way, we establish a natural generalization of the classical dimension of fibers theorem in algebraic geometry, which is interesting in its own right.
The field of descriptive combinatorics investigates the question, to what extent can classical combinatorial results and techniques be made topologically or measure-theoretically well-behaved? This paper examines a class of coloring problems induced by actions of countable groups on Polish spaces, with the requirement that the desired coloring be Baire measurable. We show that the set of all such coloring problems that admit a Baire measurable solution for a particular free action α is complete analytic (apart from the trivial situation when the orbit equivalence relation induced by α is smooth on a comeager set); this result confirms the "hardness" of finding a topologically well-behaved coloring. When α is the shift action, we characterize the class of problems for which α has a Baire measurable coloring in purely combinatorial terms; it turns out that closely related concepts have already been studied in graph theory with no relation to descriptive set theory. We remark that our framework permits a wholly dynamical interpretation (with colorings corresponding to equivariant maps to a given subshift), so this article can also be viewed as a contribution to generic dynamics.
An (r−1,1)-coloring of an r-regular graph G is an edge coloring such that each vertex is incident to r−1 edges of one color and 1 edge of a different color. In this paper, we completely characterize all 4-regular pseudographs (graphs that may contain parallel edges and loops) which do not have a (3,1)-coloring. An {r−1,1}-factor of an r-regular graph is a spanning subgraph in which each vertex has degree either r−1 or 1. We prove various conditions that that must hold for any vertex-minimal 5-regular pseudographs without (4,1)-colorings or without {4,1}-factors. Finally, for each r≥6 we construct graphs that are not (r−1,1)-colorable and, more generally, are not (r−t,t)-colorable for small t.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.