Dömötör Pálvölgyi

Almost-monochromatic sets and the chromatic number of the plane

In a colouring of $\mathbb{R}^d$ a pair $(S,s_0)$ with $S\subseteq \mathbb{R}^d$ and with $s_0\in S$ is \emph{almost monochromatic} if $S\setminus \{s_0\}$ is monochromatic but $S$ is not. We consider questions about finding almost monochromatic similar copies of pairs $(S,s_0)$ in colourings of $\mathbb{R}^d$ , $\mathbb{Z}^d$ , and in $\mathbb{Q}$ under some restrictions on the colouring. Among other results, we characterise those $(S,s_0)$ with $S\subseteq \mathbb{Z}$ for which every finite colouring of $\mathbb{R}$ without an infinite monochromatic arithmetic progression contains an almost monochromatic similar copy of $(S,s_0)$ . We also show that if $S\subseteq \mathbb{Z}^d$ and $s_0$ is outside of the convex hull of $S\setminus \{s_0\}$ , then every finite colouring of $\mathbb{R}^d$ without a similar monochromatic copy of $\mathbb{Z}^d$ contains an almost monochromatic similar copy of $(S,s_0)$ . Further, we propose an approach of finding almost-monochromatic sets that might lead to a non-computer assisted proof of $χ(\R^2)\geq 5$ .

Exchange properties of finite set-systems

In a recent breakthrough, Adiprasito, Avvakumov, and Karasev constructed a triangulation of the $n$ -dimensional real projective space with a subexponential number of vertices. They reduced the problem to finding a small downward closed set-system $\cal F$ covering an $n$ -element ground set which satisfies the following condition: For any two disjoint members $A, B\in\cal F$ , there exist $a\in A$ and $b\in B$ such that either $B\cup\{a\}\in\cal F$ and $A\cup\{b\}\setminus\{a\}\in\cal F$ , or $A\cup\{b\}\in\cal F$ and $B\cup\{a\}\setminus\{b\}\in\cal F$ . Denoting by $f(n)$ the smallest cardinality of such a family $\cal F$ , they proved that $f(n)<2^{O(\sqrt{n}\log n)}$ , and they asked for a nontrivial lower bound. It turns out that the construction of Adiprasito et al. is not far from optimal; we show that $2^{(1.42+o(1))\sqrt{n}}\le f(n)\le 2^{(1+o(1))\sqrt{2n\log n}}$ . We also study a variant of the above problem, where the condition is strengthened by also requiring that for any two disjoint members $A, B\in\cal F$ with $|A|>|B|$ , there exists $a\in A$ such that $B\cup\{a\}\in\cal F$ . In this case, we prove that the size of the smallest $\cal F$ satisfying this stronger condition lies between $2^{Ω(\sqrt{n}\log n)}$ and $2^{O(n\log\log n/\log n)}$ .

Induced and non-induced poset saturation problems

A subfamily $\mathcal{G}\subseteq \mathcal{F}\subseteq 2^{[n]}$ of sets is a non-induced (weak) copy of a poset $P$ in $\mathcal{F}$ if there exists a bijection $i:P\rightarrow \mathcal{G}$ such that $p\le_P q$ implies $i(p)\subseteq i(q)$ . In the case where in addition $p\le_P q$ holds if and only if $i(p)\subseteq i(q)$ , then $\mathcal{G}$ is an induced (strong) copy of $P$ in $\mathcal{F}$ . We consider the minimum number $sat(n,P)$ [resp.\ $sat^*(n,P)$ ] of sets that a family $\mathcal{F}\subseteq 2^{[n]}$ can have without containing a non-induced [induced] copy of $P$ and being maximal with respect to this property, i.e., the addition of any $G\in 2^{[n]}\setminus \mathcal{F}$ creates a non-induced [induced] copy of $P$ . We prove for any finite poset $P$ that $sat(n,P)\le 2^{|P|-2}$ , a bound independent of the size $n$ of the ground set. For induced copies of $P$ , there is a dichotomy: for any poset $P$ either $sat^*(n,P)\le K_P$ for some constant depending only on $P$ or $sat^*(n,P)\ge \log_2 n$ . We classify several posets according to this dichotomy, and also show better upper and lower bounds on $sat(n,P)$ and $sat^*(n,P)$ for specific classes of posets. Our main new tool is a special ordering of the sets based on the colexicographic order. It turns out that if $P$ is given, processing the sets in this order and adding the sets greedily into our family whenever this does not ruin non-induced [induced] $P$ -freeness, we tend to get a small size non-induced [induced] $P$ -saturating family.

On Communication Complexity of Fixed Point Computation

Brouwer's fixed point theorem states that any continuous function from a compact convex space to itself has a fixed point. Roughgarden and Weinstein (FOCS 2016) initiated the study of fixed point computation in the two-player communication model, where each player gets a function from $[0,1]^n$ to $[0,1]^n$ , and their goal is to find an approximate fixed point of the composition of the two functions. They left it as an open question to show a lower bound of $2^{Ω(n)}$ for the (randomized) communication complexity of this problem, in the range of parameters which make it a total search problem. We answer this question affirmatively. Additionally, we introduce two natural fixed point problems in the two-player communication model. $\bullet$ Each player is given a function from $[0,1]^n$ to $[0,1]^{n/2}$ , and their goal is to find an approximate fixed point of the concatenation of the functions. $\bullet$ Each player is given a function from $[0,1]^n$ to $[0,1]^{n}$ , and their goal is to find an approximate fixed point of the interpolation of the functions. We show a randomized communication complexity lower bound of $2^{Ω(n)}$ for these problems (for some constant approximation factor). Finally, we initiate the study of finding a panchromatic simplex in a Sperner-coloring of a triangulation (guaranteed by Sperner's lemma) in the two-player communication model: A triangulation $T$ of the $d$ -simplex is publicly known and one player is given a set $S_A\subset T$ and a coloring function from $S_A$ to $\{0,\ldots ,d/2\}$ , and the other player is given a set $S_B\subset T$ and a coloring function from $S_B$ to $\{d/2+1,\ldots ,d\}$ , such that $S_A\dot\cup S_B=T$ , and their goal is to find a panchromatic simplex. We show a randomized communication complexity lower bound of $|T|^{Ω(1)}$ for the aforementioned problem as well (when $d$ is large).

On the number of hyperedges in the hypergraph of lines and pseudo-discs

Consider the hypergraph whose vertex set is a family of $n$ lines in general position in the plane, and whose hyperedges are induced by intersections with a family of pseudo-discs. We prove that the number of $t$ -hyperedges is bounded by $O_t(n^2)$ and that the total number of hyperedges is bounded by $O(n^3)$ . Both bounds are tight.

Query complexity and the polynomial Freiman-Ruzsa conjecture

We prove a query complexity variant of the weak polynomial Freiman-Ruzsa conjecture in the following form. For any $ε> 0$ , a set $A \subset \mathbb{Z}^d$ with doubling $K$ has a subset of size at least $K^{-\frac{4}ε}|A|$ with coordinate query complexity at most $ε\log_2 |A|$ . We apply this structural result to give a simple proof of the "few products, many sums" phenomenon for integer sets. The resulting bounds are explicit and improve on the seminal result of Bourgain and Chang.

The number of tangencies between two families of curves

We prove that the number of tangencies between the members of two families, each of which consists of $n$ pairwise disjoint curves, can be as large as $Ω(n^{4/3})$ . We show that from a conjecture about forbidden $0$ - $1$ matrices it would follow that this bound is sharp for doubly-grounded families. We also show that if the curves are required to be $x$ -monotone, then the maximum number of tangencies is $Θ(n\log n)$ , which improves a result by Pach, Suk, and Treml. Finally, we also improve the best known bound on the number of tangencies between the members of a family of at most $t$ -intersecting curves.

preprint2021arXiv

Coloring Delaunay-Edges and their Generalizations

We consider geometric hypergraphs whose vertex set is a finite set of points (e.g., in the plane), and whose hyperedges are the intersections of this set with a family of geometric regions (e.g., axis-parallel rectangles). A typical coloring problem for such geometric hypergraphs asks, given an integer $k$ , for the existence of an integer $m=m(k)$ , such that every set of points can be $k$ -colored such that every hyperedge of size at least $m$ contains points of different (or all $k$ ) colors. We generalize this notion by introducing coloring of \emph{ $t$ -subsets} of points such that every hyperedge that contains enough points contains $t$ -subsets of different (or all) colors. In particular, we consider all $t$ -subsets and $t$ -subsets that are themselves hyperedges. The latter, with $t=2$ , is equivalent to coloring the edges of the so-called \emph{Delaunay-graph}. In this paper we study colorings of Delaunay-edges with respect to halfplanes, pseudo-disks, axis-parallel and bottomless rectangles, and also discuss colorings of $t$ -subsets of geometric and abstract hypergraphs, and connections between the standard coloring of vertices and coloring of $t$ -subsets of vertices.

preprint2021arXiv

On tangencies among planar curves with an application to coloring L-shapes

We prove that there are $O(n)$ tangencies among any set of $n$ red and blue planar curves in which every pair of curves intersects at most once and no two curves of the same color intersect. If every pair of curves may intersect more than once, then it is known that the number of tangencies could be super-linear. However, we show that a linear upper bound still holds if we replace tangencies by pairwise disjoint connecting curves that all intersect a certain face of the arrangement of red and blue curves. The latter result has an application for the following problem studied by Keller, Rok and Smorodinsky [Disc.\ Comput.\ Geom.\ (2020)] in the context of \emph{conflict-free coloring} of \emph{string graphs}: what is the minimum number of colors that is always sufficient to color the members of any family of $n$ \emph{grounded L-shapes} such that among the L-shapes intersected by any L-shape there is one with a unique color? They showed that $O(\log^3 n)$ colors are always sufficient and that $Ω(\log n)$ colors are sometimes necessary. We improve their upper bound to $O(\log^2 n)$ .

Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets

Suppose that the vertices of a graph $G$ are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study the problem of finding a majority vertex (or show that none exists) if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by $m(G)$ . It was shown by Saks and Werman that $m(K_n)=n-b(n)$ , where $b(n)$ is the number of 1's in the binary representation of $n$ . In this paper, we initiate the study of the problem for general graphs. The obvious bounds for a connected graph $G$ on $n$ vertices are $n-b(n)\le m(G)\le n-1$ . We show that for any tree $T$ on an even number of vertices we have $m(T)=n-1$ and that for any tree $T$ on an odd number of vertices, we have $n-65\le m(T)\le n-2$ . Our proof uses results about the weighted version of the problem for $K_n$ , which may be of independent interest. We also exhibit a sequence $G_n$ of graphs with $m(G_n)=n-b(n)$ such that $G_n$ has $O(nb(n))$ edges and $n$ vertices.

Aligned plane drawings of the generalized Delaunay-graphs for pseudo-disks

We study general Delaunay-graphs, which are natural generalizations of Delaunay triangulations to arbitrary families, in particular to pseudo-disks. We prove that for any finite pseudo-disk family and point set, there is a plane drawing of their Delaunay-graph such that every edge lies inside every pseudo-disk that contains its endpoints.

Colouring bottomless rectangles and arborescences

We study problems related to colouring bottomless rectangles. One of our main results shows that for any positive integers $m, k$ , there is no semi-online algorithm that can $k$ -colour bottomless rectangles with disjoint boundaries in increasing order of their top sides, so that any $m$ -fold covered point is covered by at least two colours. This is, surprisingly, a corollary of a stronger result for arborescence colourings. Any semi-online colouring algorithm that colours an arborescence in leaf-to-root order with a bounded number of colours produces arbitrarily long monochromatic paths. This is complemented by optimal upper bounds given by simple online colouring algorithms from other directions. Our other main results study configurations of bottomless rectangles in an attempt to improve the \textit{polychromatic $k$ -colouring number}, $m_k^*$ . We show that for many families of bottomless rectangles, such as unit-width bottomless rectangles, $m_k^*$ is linear in $k$ . We also present an improved lower bound for general families: $m_k^* \geq 2k-1$ .

Exponential lower bound for Berge-Ramsey problems

We give an exponential lower bound for Berge-Ramsey problems.

Radon numbers grow linearly

Define the $k$ -th Radon number $r_k$ of a convexity space as the smallest number (if it exists) for which any set of $r_k$ points can be partitioned into $k$ parts whose convex hulls intersect. Combining the recent abstract fractional Helly theorem of Holmsen and Lee with earlier methods of Bukh, we prove that $r_k$ grows linearly, i.e., $r_k\le c(r_2)\cdot k$ .

preprint2019arXiv

Distribution of colors in Gallai colorings

A Gallai coloring is an edge coloring that avoids triangles colored with three different colors. Given integers $e_1\ge e_2 \ge \dots \ge e_k$ with $\sum_{i=1}^ke_i={n \choose 2}$ for some $n$ , does there exist a Gallai $k$ -coloring of $K_n$ with $e_i$ edges in color $i$ ? In this paper, we give several sufficient conditions and one necessary condition to guarantee a positive answer to the above question. In particular, we prove the existence of a Gallai-coloring if $e_1-e_k\le 1$ and $k \le \lfloor n/2\rfloor$ . We prove that for any integer $k\ge 3$ there is a (unique) integer $g(k)$ with the following property: there exists a Gallai $k$ -coloring of $K_n$ with $e_i$ edges in color $i$ for every $e_1\le\dots \le e_k$ satisfying $\sum_{i=1}^ke_i={n\choose 2}$ , if and only if $n\ge g(k)$ . We show that $g(3)=5$ , $g(4)=8$ , and $2k-2\le g(k)\le 8k^2+1$ for every $k\ge 3$ .

preprint2016arXiv

Finding a non-minority ball with majority answers

Suppose we are given a set of $n$ balls $\{b_1,\ldots,b_n\}$ each colored either red or blue in some way unknown to us. To find out some information about the colors, we can query any triple of balls $\{b_{i_1},b_{i_2},b_{i_3}\}$ . As an answer to such a query we obtain (the index of) a {\em majority ball}, that is, a ball whose color is the same as the color of another ball from the triple. Our goal is to find a {\em non-minority ball}, that is, a ball whose color occurs at least $\frac n2$ times among the $n$ balls. We show that the minimum number of queries needed to solve this problem is $Θ(n)$ in the adaptive case and $Θ(n^3)$ in the non-adaptive case. We also consider some related problems.

Clustered planarity testing revisited

The Hanani--Tutte theorem is a classical result proved for the first time in the 1930s that characterizes planar graphs as graphs that admit a drawing in the plane in which every pair of edges not sharing a vertex cross an even number of times. We generalize this result to clustered graphs with two disjoint clusters, and show that a straightforward extension to flat clustered graphs with three or more disjoint clusters is not possible. For general clustered graphs we show a variant of the Hanani--Tutte theorem in the case when each cluster induces a connected subgraph. Di Battista and Frati proved that clustered planarity of embedded clustered graphs whose every face is incident with at most five vertices can be tested in polynomial time. We give a new and short proof of this result, using the matroid intersection algorithm.

More on Decomposing Coverings by Octants

In this note we improve our upper bound given earlier by showing that every 9-fold covering of a point set in the space by finitely many translates of an octant decomposes into two coverings, and our lower bound by a construction for a 4-fold covering that does not decompose into two coverings. The same bounds also hold for coverings of points in $\R^2$ by finitely many homothets or translates of a triangle. We also prove that certain dynamic interval coloring problems are equivalent to the above question.

Online and quasi-online colorings of wedges and intervals

We consider proper online colorings of hypergraphs defined by geometric regions. We prove that there is an online coloring algorithm that colors $N$ intervals of the real line using $Θ(\log N/k)$ colors such that for every point $p$ , contained in at least $k$ intervals, not all the intervals containing $p$ have the same color. We also prove the corresponding result about online coloring a family of wedges (quadrants) in the plane that are the translates of a given fixed wedge. These results contrast the results of the first and third author showing that in the quasi-online setting 12 colors are enough to color wedges (independent of $N$ and $k$ ). We also consider quasi-online coloring of intervals. In all cases we present efficient coloring algorithms.

Regular families of forests, antichains and duality pairs of relational structures

Homomorphism duality pairs play crucial role in the theory of relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully characterized. The case when both side are infinite seems to be very complex. It is also known that no finite-infinite duality pair is possible if we make the additional restriction that both classes are antichains. In this paper we characterize the infinite-finite antichain dualities and infinite-finite dualities with trees or forest on the left hand side. This work builds on our earlier papers that gave several examples of infinite-finite antichain duality pairs of directed graphs and a complete characterization for caterpillar dualities.

Unsplittable coverings in the plane

A system of sets forms an {\em $m$ -fold covering} of a set $X$ if every point of $X$ belongs to at least $m$ of its members. A $1$ -fold covering is called a {\em covering}. The problem of splitting multiple coverings into several coverings was motivated by classical density estimates for {\em sphere packings} as well as by the {\em planar sensor cover problem}. It has been the prevailing conjecture for 35 years (settled in many special cases) that for every plane convex body $C$ , there exists a constant $m=m(C)$ such that every $m$ -fold covering of the plane with translates of $C$ splits into $2$ coverings. In the present paper, it is proved that this conjecture is false for the unit disk. The proof can be generalized to construct, for every $m$ , an unsplittable $m$ -fold covering of the plane with translates of any open convex body $C$ which has a smooth boundary with everywhere {\em positive curvature}. Somewhat surprisingly, {\em unbounded} open convex sets $C$ do not misbehave, they satisfy the conjecture: every $3$ -fold covering of any region of the plane by translates of such a set $C$ splits into two coverings. To establish this result, we prove a general coloring theorem for hypergraphs of a special type: {\em shift-chains}. We also show that there is a constant $c>0$ such that, for any positive integer $m$ , every $m$ -fold covering of a region with unit disks splits into two coverings, provided that every point is covered by {\em at most} $c2^{m/2}$ sets.

Convex Polygons are Self-Coverable

We introduce a new notion for geometric families called self-coverability and show that homothets of convex polygons are self-coverable. As a corollary, we obtain several results about coloring point sets such that any member of the family with many points contains all colors. This is dual (and in some cases equivalent) to the much investigated cover-decomposability problem.

Domination in transitive colorings of tournaments

An edge coloring of a tournament $T$ with colors $1,2,\dots,k$ is called \it $k$ -transitive \rm if the digraph $T(i)$ defined by the edges of color $i$ is transitively oriented for each $1\le i \le k$ . We explore a conjecture of the second author: For each positive integer $k$ there exists a (least) $p(k)$ such that every $k$ -transitive tournament has a dominating set of at most $p(k)$ vertices. We show how this conjecture relates to other conjectures and results. For example, it is a special case of a well-known conjecture of Erd\H os, Sands, Sauer and Woodrow (so the conjecture is interesting even if false). We show that the conjecture implies a stronger conjecture, a possible extension of a result of Bárány and Lehel on covering point sets by boxes. The principle used leads also to an upper bound $O(2^{2^{d-1}}d\log d)$ on the $d$ -dimensional box-cover number that is better than all previous bounds, in a sense close to best possible. We also improve the best bound known in 3-dimensions from $3^{14}$ to 64 and propose possible further improvements through finding the maximum domination number over parity tournaments.

Forbidden hypermatrices imply general bounds on induced forbidden subposet problems

We prove that for every poset $P$ , there is a constant $C$ such that the size of any family of subsets of $[n]$ that does not contain $P$ as an induced subposet is at most $C{\binom{n}{\lfloor\frac{n}{2}\rfloor}}$ , settling a conjecture of Katona, and Lu and Milans. We obtain this bound by establishing a connection to the theory of forbidden submatrices and then applying a higher dimensional variant of the Marcus-Tardos theorem, proved by Klazar and Marcus. We also give a new proof of their result.

On the Tree Search Problem with Non-uniform Costs

Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indexes, as well as in hierarchy based knowledge representation. In this paper we focus on tree-like partial orders and consider the problem of identifying an initially unknown vertex in a tree by asking edge queries: an edge query $e$ returns the component of $T-e$ containing the vertex sought for, while incurring some known cost $c(e)$ . The Tree Search Problem with Non-Uniform Cost is: given a tree $T$ where each edge has an associated cost, construct a strategy that minimizes the total cost of the identification in the worst case. Finding the strategy guaranteeing the minimum possible cost is an NP-complete problem already for input tree of degree 3 or diameter 6. The best known approximation guarantee is the $O(\log n/\log \log \log n)$ -approximation algorithm of [Cicalese et al. TCS 2012]. We improve upon the above results both from the algorithmic and the computational complexity point of view: We provide a novel algorithm that provides an $O(\frac{\log n}{\log \log n})$ -approximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NP-complete even when the input tree is a spider, i.e., at most one vertex has degree larger than 2.

Bin Packing via Discrepancy of Permutations

A well studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most O(log n) additional bins. The three-permutations-problem of Beck is the following. Given any 3 permutations on n symbols, color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols is roughly the same. The necessary difference is called the discrepancy. We establish a surprising connection between bin packing and Beck's problem: The additive integrality gap of the 3-partition linear programming relaxation can be bounded by the discrepancy of 3 permutations. Reversely, making use of a recent example of 3 permutations, for which a discrepancy of Omega(log n) is necessary, we prove the following: The O(log^2 n) upper bound on the additive gap for bin packing with arbitrary item sizes cannot be improved by any technique that is based on rounding up items. This lower bound holds for a large class of algorithms including the Karmarkar-Karp procedure.

Density-based group testing

In this paper we study a new, generalized version of the well-known group testing problem. In the classical model of group testing we are given n objects, some of which are considered to be defective. We can test certain subsets of the objects whether they contain at least one defective element. The goal is usually to find all defectives using as few tests as possible. In our model the presence of defective elements in a test set Q can be recognized if and only if their number is large enough compared to the size of Q. More precisely for a test Q the answer is 'yes' if and only if there are at least α|Q| defective elements in Q for some fixed α.

Majority and Plurality Problems

Given a set of n balls each colored with a color, a ball is said to be majority, k-majority, plurality if its color class has size larger than half of the number of balls, has size at least k, has size larger than any other color class; respectively. We address the problem of finding the minimum number of queries (a comparison of a pair of balls if they have the same color or not) that is needed to decide whether a majority, k-majority or plurality ball exists and if so then show one such ball. We consider both adaptive and non-adaptive strategies and in certain cases, we also address weighted versions of the problems.

Octants are Cover-Decomposable into Many Coverings

We prove that octants are cover-decomposable into multiple coverings, i.e., for any k there is an m(k) such that any m(k)-fold covering of any subset of the space with a finite number of translates of a given octant can be decomposed into k coverings. As a corollary, we obtain that any m(k)-fold covering of any subset of the plane with a finite number of homothetic copies of a given triangle can be decomposed into k coverings. Previously only some weaker bounds were known for related problems.

Drawing cubic graphs with the four basic slopes

We show that every cubic graph can be drawn in the plane with straight-line edges using only the four basic slopes $\{0,π/4,π/2,3π/4\}$ . We also prove that four slopes have this property if and only if we can draw $K_4$ with them.

Lower bounds for finding the maximum and minimum elements with k lies

In this paper we deal with the problem of finding the smallest and the largest elements of a totally ordered set of size $n$ using pairwise comparisons if $k$ of the comparisons might be erroneous where $k$ is a fixed constant. We prove that at least $(k+1.5)n+Θ(k)$ comparisons are needed in the worst case thus disproving the conjecture that $(k+1+ε)n$ comparisons are enough.

Lower bounds on the obstacle number of graphs

Given a graph $G$ , an {\em obstacle representation} of $G$ is a set of points in the plane representing the vertices of $G$ , together with a set of connected obstacles such that two vertices of $G$ are joined by an edge if and only if the corresponding points can be connected by a segment which avoids all obstacles. The {\em obstacle number} of $G$ is the minimum number of obstacles in an obstacle representation of $G$ . It is shown that there are graphs on $n$ vertices with obstacle number at least $Ω({n}/{\log n})$ .

Octants are Cover Decomposable

We prove that octants are cover-decomposable, i.e., any 12-fold covering of any subset of the space with a finite number of translates of a given octant can be decomposed into two coverings. As a corollary, we obtain that any 12-fold covering of any subset of the plane with a finite number of homothetic copies of a given triangle can be decomposed into two coverings. We also show that any 12-fold covering of the whole plane with open triangles can be decomposed into two coverings. However, we exhibit an indecomposable 3-fold covering.

Saturating Sperner families

A family $\cF \subseteq 2^{[n]}$ saturates the monotone decreasing property $\cP$ if $\cF$ satisfies $\cP$ and one cannot add any set to $\cF$ such that property $\cP$ is still satisfied by the resulting family. We address the problem of finding the minimum size of a family saturating the $k$ -Sperner property and the minimum size of a family that saturates the Sperner property and that consists only of $l$ -sets and $(l+1)$ -sets.

Communication Complexity

The first section starts with the basic definitions following mainly the notations of the book written by E. Kushilevitz and N. Nisan. At the end of the first section I examine tree-balancing. In the second section I summarize the well-known lower bound methods and prove the exact complexity of certain functions. In the first part of the third section I introduce the random complexity and prove the basic lemmas about it. In the second part I prove a better lower bound for the complexity of all random functions. In the third part I introduce and compare several upper bounds for the complexity of the identity function. In the fourth section I examine the well-known Direct-sum conjecture. I introduce a different model of computation then prove that it is the same as the original one up to a constant factor. This new model is used to bound the Amortized Time Complexity of a function by the number of the leaves of its protocol-tree. After this I examine the Direct-sum problem in case of Partial Information and in the Random case. In the last section I introduce the well-known hierarchy classes, the reducibility and the completeness of series of functions. Then I define the class PSPACE and Oracles in the communication complexity model and prove some basic claims about them.

Consistent digital line segments

We introduce a novel and general approach for digitalization of line segments in the plane that satisfies a set of axioms naturally arising from Euclidean axioms. In particular, we show how to derive such a system of digital segments from any total order on the integers. As a consequence, using a well-chosen total order, we manage to define a system of digital segments such that all digital segments are, in Hausdorff metric, optimally close to their corresponding Euclidean segments, thus giving an explicit construction that resolves the main question of Chun et al.

Decomposition of Geometric Set Systems and Graphs

We study two decomposition problems in combinatorial geometry. The first part deals with the decomposition of multiple coverings of the plane. We say that a planar set is cover-decomposable if there is a constant m such that any m-fold covering of the plane with its translates is decomposable into two disjoint coverings of the whole plane. Pach conjectured that every convex set is cover-decomposable. We verify his conjecture for polygons. Moreover, if m is large enough, we prove that any m-fold covering can even be decomposed into k coverings. Then we show that the situation is exactly the opposite in 3 dimensions, for any polyhedron and any $m$ we construct an m-fold covering of the space that is not decomposable. We also give constructions that show that concave polygons are usually not cover-decomposable. We start the first part with a detailed survey of all results on the cover-decomposability of polygons. The second part investigates another geometric partition problem, related to planar representation of graphs. The slope number of a graph G is the smallest number s with the property that G has a straight-line drawing with edges of at most s distinct slopes and with no bends. We examine the slope number of bounded degree graphs. Our main results are that if the maximum degree is at least 5, then the slope number tends to infinity as the number of vertices grows but every graph with maximum degree at most 3 can be embedded with only five slopes. We also prove that such an embedding exists for the related notion called slope parameter. Finally, we study the planar slope number, defined only for planar graphs as the smallest number s with the property that the graph has a straight-line drawing in the plane without any crossings such that the edges are segments of only s distinct slopes. We show that the planar slope number of planar graphs with bounded degree is bounded.