We investigate local computation algorithms (LCA) for two-coloring of $k$-uniform hypergraphs. We focus on hypergraph instances that satisfy strengthened assumption of the Lovász Local Lemma of the form $2^{1-αk} (Δ+1) \mathrm{e} < 1$, where $Δ$ is the bound on the maximum edge degree. The main question which arises here is for how large $α$ there exists an LCA that is able to properly color such hypergraphs in polylogarithmic time per query. We describe briefly how upgrading the classical sequential procedure of Beck from 1991 with Moser and Tardos' RESAMPLE yields polylogarithmic LCA that works for $α$ up to $1/4$. Then, we present an improved procedure that solves wider range of instances by allowing $α$ up to $1/3$.

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(k^2\; 2^k)$. 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 $2^{k+Θ(k^{2/3})}$ edges. Applying derandomization technique we reduce that number to $2^{k+\widetildeΘ(k^{1/2})}$.

For a hypergraph $H$, let $q(H)$ denote the expected number of monochromatic edges when the color of each vertex in $H$ is sampled uniformly at random from the set of size 2. Let $s_{\min}(H)$ denote the minimum size of an edge in $H$. Erdős asked in 1963 whether there exists an unbounded function $g(k)$ such that any hypergraph $H$ with $s_{\min}(H) \geq k$ and $q(H) \leq g(k)$ is two colorable. Beck in 1978 answered this question in the affirmative for a function $g(k) = Θ(\log^* k)$. We improve this result by showing that, for an absolute constant $δ>0$, a version of random greedy coloring procedure is likely to find a proper two coloring for any hypergraph $H$ with $s_{\min}(H) \geq k$ and $q(H) \leq δ\cdot \log k$.

Several classical constructions illustrate the fact that the chromatic number of a graph may 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 $$\mathbb{R }^2$$ that is not an axis-aligned rectangle and for any positive integer $$k$$ produces a family $$\mathcal{F }$$ of sets, each obtained by an independent horizontal and vertical scaling and translation of $$X$$ , such that no three sets in $$\mathcal{F }$$ pairwise intersect and $$\chi (\mathcal{F })>k$$ . This provides a negative answer to a question of Gyárfás 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 or 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.

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 three 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 $L_v$. A coloring is chosen from $\{{L_v}_{v\in V(G)}\}$ if the color of each $v$ belongs to $L_v$. The Thue choice number of $G$, denoted by $\pi_l(G)$, is the minimum $k$ such that for any list assignment $\{{L_v}\}$ of $G$ with each $|{L_v}|\geqslant k$ there is a nonrepetitive coloring of $G$ chosen from $\{{L_v}\}$. Alon et al. proved in 2002 that $\pi_l(G)=O(\Delta^2)$ for every graph $G$ with maximum degree at most $\Delta$. We propose an almost linear bound in $\Delta$ for trees, namely, for any $\varepsilon>0$ there is a constant $c$ such that $\pi_l(T)\leqslant c\Delta^{1+\varepsilon}$ for every tree $T$ with maximum degree $\Delta$. The only lower bound for trees is given by a recent result of Fiorenzi et al. that for any $\Delta$ there is a tree $T$ such that $\pi_l(T)=\Omega(\frac{\log\Delta}{\log \log \Delta})$. We also show that if one allows repetitions in a coloring but still forbids three identical consecutive blocks of colors on any simple path, then a constant size of the lists allows one to color any tree.