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
In 1964 Erdős proved, by randomized construction, that the minimum number of edges in a k-graph that is not two colorable is O(k22k). To this day, it is not known whether there exist such k-graphs with smaller number of edges. Known deterministic constructions use much larger number of edges. The most recent one by Gebauer requires 2k+Θ(k2/3) edges. Applying derandomization technique we reduce that number to 2k+Θ(k1/2).
In 1964 Erdős proved that $(1+\oh{1})) \frac{\eul \ln(2)}{4} k^2 2^{k}$ edges are sufficient to build a k-graph which is not two colorable. To this day, it is not known whether there exist such k-graphs with smaller number of edges. Erdős' bound is consequence of the fact that a hypergraph with k2/2 vertices and $M(k)=(1+\oh{1}) \frac{\eul \ln(2)}{4} k^2 2^{k}$ randomly chosen edges of size k is asymptotically almost surely not two colorable. Our first main result implies that for any ε>0, any k-graph with (1−ε)M(k) randomly and uniformly chosen edges is a.a.s. two colorable. The presented proof is an adaptation of the second moment method analogous to the developments of Achlioptas and Moore from 2002 who considered the problem with fixed size of edges and number of vertices tending to infinity. In the second part of the paper we consider the problem of algorithmic coloring of random k-graphs. We show that quite simple, and somewhat greedy procedure, a.a.s. finds a proper two coloring for random k-graphs on k2/2 vertices, with at most $\Oh{k\ln k\cdot 2^k}$ edges. That is of the same asymptotic order as the analogue of the \emph{algorithmic barrier} defined by Achlioptas and Coja-Oghlan in 2008, for the case of fixed k.
The paper deals with extremal problems concerning colorings of hypergraphs. By using a random recoloring algorithm we show that any n-uniform simple (i.e. every two distinct edges share at most one vertex) hypergraph H with maximum edge degree at most Δ(H)≤c⋅nrn−1, is r-colorable, where c>0 is an absolute constant. %We prove also that similar result holds for b-simple hypergraphs. As an application of our proof technique we establish a new lower bound for Van der Waerden number W(n,r), the minimum N such that in any r-coloring of the set {1,...,N} there exists a monochromatic arithmetic progression of length n. We show that W(n,r)>c⋅rn−1, for some absolute constant c>0.
Let m∗(n) be the minimum number of edges in an n-uniform simple hypergraph that is not two colorable. We prove that m∗(n)=Ω(4n/ln2(n)). Our result generalizes to r-coloring of b-simple uniform hypergraphs. For fixed r and b we prove that a maximum vertex degree in b-simple n-uniform hypergraph that is not r-colorable must be Ω(rn/ln(n)). By trimming arguments it implies that every such graph has Ω((rn/ln(n))b+1/b) edges. For any fixed r≥2 our techniques yield also a lower bound Ω(rn/ln(n)) for van der Waerden numbers W(n,r).
Several classical constructions illustrate the fact that the chromatic number of a graph can be arbitrarily large compared to its clique number. However, until very recently, no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set X in R2 that is not an axis-aligned rectangle and for any positive integer k produces a family F of sets, each obtained by an independent horizontal and vertical scaling and translation of X, such that no three sets in F pairwise intersect and χ(F)>k. This provides a negative answer to a question of Gyarfas and Lehel for L-shapes. With extra conditions, we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries, and equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.
In the 1970s, Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is no. Specifically, for each positive integer k, we construct a triangle-free family of line segments in the plane with chromatic number greater than k. Our construction disproves a conjecture of Scott that graphs excluding induced subdivisions of any fixed graph have chromatic number bounded by a function of their clique number.
The smallest number of edges forming an n-uniform hypergraph which is not r-colorable is denoted by m(n,r). Erdős and Lovász conjectured that m(n,2)=θ(n 2^n)$. The best known lower bound m(n,2)=Ω(sqrt(n/log(n)) 2^n) was obtained by Radhakrishnan and Srinivasan in 2000. We present a simple proof of their result. The proof is based on analysis of random greedy coloring algorithm investigated by Pluhár in 2009. The proof method extends to the case of r-coloring, and we show that for any fixed r we have m(n,r)=Ω((n/log(n))^(1-1/r) r^n) improving the bound of Kostochka from 2004. We also derive analogous bounds on minimum edge degree of an n-uniform hypergraph that is not r-colorable.
A nonrepetitive coloring of a path is a coloring of its vertices such that the sequence of colors along the path does not contain two identical, consecutive blocks. The remarkable construction of Thue asserts that 3 colors are enough to color nonrepetitively paths of any length. A nonrepetitive coloring of a graph is a coloring of its vertices such that all simple paths are nonrepetitively colored. Assume that each vertex v of a graph G has assigned a set (list) of colors Lv. A coloring is chosen from {Lv}v∈V(G) if the color of each v belongs to Lv. The Thue choice number of G, denoted by πl(G), is the minimum k such that for any list assignment {Lv} of G with each ∣Lv∣≥k there is a nonrepetitive coloring of G chosen from {Lv}. Alon et al. (2002) proved that πl(G)=O(Δ2) for every graph G with maximum degree at most Δ. We propose an almost linear bound in Δ for trees, namely for any $\epsi>0$ there is a constant c such that $π_l(T)\leq cΔ^{1+\epsi}$ for every tree T with maximum degree Δ. The only lower bound for trees is given by a recent result of Fiorenzi et al. (2011) that for any Δ there is a tree T such that πl(T)=Ω(loglogΔlogΔ). We also show that if one allows repetitions in a coloring but still forbid 3 identical consecutive blocks of colors on any simple path, then a constant size of the lists allows to color any tree.
The on-line choice number of a graph is a variation of the choice number defined through a two person game. It is at least as large as the choice number for all graphs and is strictly larger for some graphs. In particular, there are graphs G with ∣V(G)∣=2χ(G)+1 whose on-line choice numbers are larger than their chromatic numbers, in contrast to a recently confirmed conjecture of Ohba that every graph G with ∣V(G)∣≤2χ(G)+1 has its choice number equal its chromatic number. Nevertheless, an on-line version of Ohba conjecture was proposed in [P. Huang, T. Wong and X. Zhu, Application of polynomial method to on-line colouring of graphs, European J. Combin., 2011]: Every graph G with ∣V(G)∣≤2χ(G) has its on-line choice number equal its chromatic number. This paper confirms the on-line version of Ohba conjecture for graphs G with independence number at most 3. We also study list colouring of complete multipartite graphs K3⋆k with all parts of size 3. We prove that the on-line choice number of K3⋆k is at most 3/2k, and present an alternate proof of Kierstead's result that its choice number is ⌈(4k−1)/3⌉. For general graphs G, we prove that if ∣V(G)∣≤χ(G)+χ(G) then its on-line choice number equals chromatic number.
A sequence is nonrepetitive if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that 3 symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of 3-element sets L1,...,Ln there exists a nonrepetitive sequence s1,...,sn with si∈Li. Applying the probabilistic method one can prove that this is true for sufficiently large sets Li. We present an elementary proof that sets of size 4 suffice (confirming the best known bound). The argument is a simple counting with Catalan numbers involved. Our approach is inspired by a new algorithmic proof of the Lovász Local Lemma due to Moser and Tardos and its interpretations by Fortnow and Tao. The presented method has further applications to nonrepetitive games and nonrepetitive colorings of graphs.
(Note. The results of this manuscript has been merged and published with another paper of the same authors: A new approach to nonrepetitve sequences.) A repetition of size h (h⩾1) in a given sequence is a subsequence of consecutive terms of the form: xx=x1...xhx1...xh. A sequence is nonrepetitive if it does not contain a repetition of any size. The remarkable construction of Thue asserts that 3 different symbols are enough to build an arbitrarily long nonrepetitive sequence. We consider game-theoretic versions of results on nonrepetitive sequences. A nonrepetitive game is played by two players who pick, one by one, consecutive terms of a sequence over a given set of symbols. The first player tries to avoid repetitions, while the second player, in contrast, wants to create them. Of course, by simple imitation, the second player can force lots of repetitions of size 1. However, as proved by Pegden, there is a strategy for the first player to build an arbitrarily long sequence over 37 symbols with no repetitions of size >1. Our techniques allow to reduce 37 to 6. Another game we consider is an erase-repetition game. Here, whenever a repetition occurs, the repeated block is immediately erased and the next player to move continues the play. We prove that there is a strategy for the first player to build an arbitrarily long nonrepetitive sequence over 8 symbols. Our approach is inspired by a new algorithmic proof of the Lovász Local Lemma due to Moser and Tardos and previous work of Moser (his so called entropy compression argument).
A sequence S=s1s2...n is \emph{nonrepetitive} if no two adjacent blocks of S are identical. In 1906 Thue proved that there exist arbitrarily long nonrepetitive sequences over 3-element set of symbols. We study a generalization of nonrepetitive sequences involving arithmetic progressions. We prove that for every k⩾1 and every c⩾1 there exist arbitrarily long sequences over at most (1+c1)k+18kc/c+1 symbols whose subsequences indexed by arithmetic progressions with common differences from the set {1,2,...,k} are nonrepetitive. This improves a previous bound obtained in \cite{Grytczuk Rainbow}. Our approach is based on a technique introduced recently in \cite{GrytczukKozikMicek}, which was originally inspired by a constructive proof of the Lovász Local Lemma due to Moser and Tardos \cite{MoserTardos}. We also discuss some related problems that can be successfully attacked by this method.
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.