Search

Assume two finite families $\mathcal A$ and $\mathcal B$ of convex sets in $\mathbb{R}^3$ have the property that $A\cap B\ne \emptyset$ for every $A \in \mathcal A$ and $B\in \mathcal B$. Is there a constant $\gamma >0$ (independent of $\mathcal A$ and $\mathcal B$) such that there is a line intersecting $\gamma|\mathcal A|$ sets in $\mathcal A$ or $\gamma|\mathcal B|$ sets in $\mathcal B$? This is an intriguing Helly-type question from a paper by Mart\'{i}nez, Roldan and Rubin. We confirm this in the special case when all sets in $\mathcal A$ lie in parallel planes and all sets in $\mathcal B$ lie in parallel planes; in fact, all sets from one of the two families has a line transversal.

The study of geometric hypergraphs gave rise to the notion of $ABAB$-free hypergraphs. A hypergraph $\mathcal{H}$ is called $ABAB$-free if there is an ordering of its vertices such that there are no hyperedges $A,B$ and vertices $v_1,v_2,v_3,v_4$ in this order satisfying $v_1,v_3\in A\setminus B$ and $v_2,v_4\in B\setminus A$. In this paper, we prove that it is NP-complete to decide if a hypergraph is $ABAB$-free. We show a number of analogous results for hypergraphs with similar forbidden patterns, such as $ABABA$-free hypergraphs. As an application, we show that deciding whether a hypergraph is realizable as the incidence hypergraph of points and pseudodisks is also NP-complete., Comment: 10 pages

Geometric motivations warranted the study of hypergraphs on ordered vertices that have no pair of hyperedges that induce an alternation of some given length. Such hypergraphs are called ABA-free, ABAB-free and so on. Since then various coloring and other combinatorial results were proved about these families of hypergraphs. We prove a characterization in terms of their incidence matrices which avoids using the ordering of the vertices. Using this characterization, we prove new results about the dual hypergraphs of ABAB-free hypergraphs. In particular, we show that dual-ABAB-free hypergraphs are not always proper $2$-colorable even if we restrict ourselves to hyperedges that are larger than some parameter $m$.

We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant $\epsilon\in (0,1)$, one could construct a $(2+\epsilon)$-spanner with $O(n\log(n))$ edges (SICOMP 2019), and there is a lower bound of $\Omega(n^2)$ edges for any $(2-\epsilon)$-spanner (SoCG 2015). The main open question is whether a linear number of edges suffices and the stretch can be reduced to $2$. We resolve this problem by showing that for stretch $2$, one needs $\Omega(n\log n)$ edges, and for stretch $2+\epsilon$ for any fixed $\epsilon \in (0,1)$, $O(n)$ edges are sufficient. Our lower bound is the first super-linear lower bound for stretch $2$. En route to achieve our result, we introduce the problem of constructing non-Steiner tree covers for metrics, which is a natural variant of the well-known Steiner point removal problem for trees (SODA 2001). Given a tree and a set of terminals in the tree, our goal is to construct a collection of a small number of dominating trees such that for every two points, at least one tree in the collection preserves their distance within a small stretch factor. Here, we identify an unexpected threshold phenomenon around $2$ where a sharp transition from $n$ trees to $\Theta(\log n)$ trees and then to $O(1)$ trees happens. Specifically, (i) for stretch $ 2-\epsilon$, one needs $\Omega(n)$ trees; (ii) for stretch $2$, $\Theta(\log n)$ tree is necessary and sufficient; and (iii) for stretch $2+\epsilon$, a constant number of trees suffice. Furthermore, our lower bound technique for the non-Steiner tree covers of stretch $2$ has further applications in proving lower bounds for two related constructions in tree metrics: reliable spanners and locality-sensitive orderings. Our lower bound for locality-sensitive orderings matches the best upper bound (STOC 2022)., Comment: 40 pages, 11 figures. Abstract shorten to meet Arxiv limits

We prove fractional Helly and $(p,k+2)$-theorems for $k$-flats intersecting Euclidean balls. For example, we show that if for a collection of balls from $\mathbb R^d$ any $p$ balls have a $k$-flat that intersects at least $k+2$ of them, then the whole collection can be intersected by bounded many $k$-flats. We prove colorful, spherical, and infinite variants as well. In fact, we prove that fractional Helly and $(p,q)$-theorems imply $(\aleph_0,q)$-theorems in an entirely abstract setting. The fractional Helly theorems generalize to other fat objects as well., Comment: We corrected the statements of Corollaries 19, 20 and 22, and added an example after Corollary 19. The proofs needed no modification

Extending the notion of sunflowers, we call a family of at least two sets an odd-sunflower if every element of the underlying set is contained in an odd number of sets or in none of them. It follows from the Erd\H os--Szemer\'edi conjecture, recently proved by Naslund and Sawin, that there is a constant $\mu<2$ such that every family of subsets of an $n$-element set that contains no odd-sunflower consists of at most $\mu^n$ sets. We construct such families of size at least $1.5021^n$. We also characterize minimal odd-sunflowers of triples.

In a graph $G$, the $2$-neighborhood of a vertex set $X$ consists of all vertices of $G$ having at least $2$ neighbors in $X$. We say that a bipartite graph $G(A,B)$ satisfies the double Hall property if $|A|\geq2$, and every subset $X \subseteq A$ of size at least $2$ has a $2$-neighborhood of size at least $|X|$. Salia conjectured that any bipartite graph $G(A,B)$ satisfying the double Hall property contains a cycle covering $A$. Here, we prove the existence of a $2$-factor covering $A$ in any bipartite graph $G(A,B)$ satisfying the double Hall property. We also show Salia's conjecture for graphs with restricted degrees of vertices in $B$. Additionally, we prove a lower bound on the number of edges in a graph satisfying the double Hall property, and the bound is sharp up to a constant factor., Comment: minor corrections; to be published in Discrete Mathematics

We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to compute its value, even if we know beforehand that the number of 0's and 1's in the input are the same, i.e., when our input is from the middle slice. This answers a question of Byramji. Our proof is non-constructive, but we also propose a concrete candidate function that might have the above property. Our results are related to certain natural discrepancy type questions that, somewhat surprisingly, have not been studied before., Comment: 11 pages

We exhibit a 5-uniform hypergraph that has no polychromatic 3-coloring, but all its restricted subhypergraphs with edges of size at least 3 are 2-colorable. This disproves a bold conjecture of Keszegh and the author, and can be considered as the first step to understand polychromatic colorings of hereditary hypergraph families better since the seminal work of Berge. We also show that our method cannot give hypergraphs of arbitrary high uniformity, and mention some connections to panchromatic colorings.

We introduce two variants of the poset saturation problem. For a poset $P$ and the Boolean lattice $\mathcal{B}_n$, a family $\mathcal{F}$ of sets, not necessarily from $\mathcal{B}_n$, is \textit{projective $P$-saturated} if (i) it does not contain any strong copies of $P$, (ii) for any $G\in \mathcal{B}_n\setminus \mathcal{F}$, the family $\mathcal{F}\cup \{G\}$ contains a strong copy of $P$, and (iii) for any two different $F,F'\in\mathcal{F}$ we have $F\cap[n]\neq F'\cap [n]$. Ordinary strongly $P$-saturated families, i.e., subfamilies $\mathcal{F}$ required to be from $\mathcal{B}_n$ satisfying (i) and (ii), automatically satisfy (iii) as they lie within $\mathcal{B}_n$. We study what phenomena are valid both for the ordinary saturation number $\mathrm{sat}^*(n,P)$ and the projective saturation number, the size of the smallest projective $P$-saturated family. Note that the projective saturation number might differ for a poset and its dual. We also introduce an even more relaxed and symmetric version of poset saturation, \textit{external saturation}. We conjecture that all finite posets have bounded external saturation number, and prove this in some special cases.

We introduce partitioned matching games as a suitable model for international kidney exchange programmes, where in each round the total number of available kidney transplants needs to be distributed amongst the participating countries in a "fair" way. A partitioned matching game $(N,v)$ is defined on a graph $G=(V,E)$ with an edge weighting $w$ and a partition $V=V_1 \cup \dots \cup V_n$. The player set is $N = \{1, \dots, n\}$, and player $p \in N$ owns the vertices in $V_p$. The value $v(S)$ of a coalition $S \subseteq N$ is the maximum weight of a matching in the subgraph of $G$ induced by the vertices owned by the players in $S$. If $|V_p|=1$ for all $p\in N$, then we obtain the classical matching game. Let $c=\max\{|V_p| \; |\; 1\leq p\leq n\}$ be the width of $(N,v)$. We prove that checking core non-emptiness is polynomial-time solvable if $c\leq 2$ but co-NP-hard if $c\leq 3$. We do this via pinpointing a relationship with the known class of $b$-matching games and completing the complexity classification on testing core non-emptiness for $b$-matching games. With respect to our application, we prove a number of complexity results on choosing, out of possibly many optimal solutions, one that leads to a kidney transplant distribution that is as close as possible to some prescribed fair distribution.

We study $\mathrm{exa}_k(n,F)$, the largest number of edges in an $n$-vertex graph $G$ that contains exactly $k$ copies of a given subgraph $F$. The case $k=0$ is the Tur\'an number $\mathrm{ex}(n,F)$ that is among the most studied parameters in extremal graph theory. We show that for any $F$ and $k$, $\mathrm{exa}_k(n,F)=(1+o(1))\mathrm{ex}(n,F))$ and determine the exact values of $\mathrm{exa}_k(n,K_3)$ and $\mathrm{exa}_1(n,K_r)$ for $n$ large enough. We also explore a connection to the following well-known problem in search theory. We are given a graph of order $n$ that consists of an unknown copy of $F$ and some isolated vertices. We can ask pairs of vertices as queries, and the answer tells us whether there is an edge between those vertices. Our goal is to describe the graph using as few queries as possible. Aigner and Triesch in 1990 showed that the number of queries needed is at least $\binom{n}{2}-\mathrm{exa}_1(n,F)$. Among other results we show that the number of queries that were answered NO is at least $\binom{n}{2}-\mathrm{exa}_1(n,F)$., Comment: 15 pages

We study systems of orientations on triples that satisfy the following so-called interiority condition: $\circlearrowleft(ABD)=~\circlearrowleft(BCD)=~\circlearrowleft(CAD)=1$ implies $\circlearrowleft(ABC)=1$ for any $A,B,C,D$. We call such an orientation a P3O (partial 3-order), a natural generalization of a poset, that has several interesting special cases. For example, the order type of a planar point set (that can have collinear triples) is a P3O; we denote a P3O realizable by points as p-P3O. If we do not allow $\circlearrowleft(ABC)=0$, we obtain a T3O (total 3-order). Contrary to linear orders, a T3O can have a rich structure. A T3O realizable by points, a p-T3O, is the order type of a point set in general position. In our paper "Orientation of convex sets" we defined a 3-order on pairwise intersecting convex sets; such a P3O is called a C-P3O. In this paper we extend this 3-order to pairwise intersecting good covers; such a P3O is called a GC-P3O. If we do not allow $\circlearrowleft(ABC)=0$, we obtain a C-T3O and a GC-T3O, respectively. The main result of this paper is that there is a p-T3O that is not a GC-T3O, implying also that it is not a C-T3O -- this latter problem was left open in our earlier paper. Our proof involves several combinatorial and geometric observations that can be of independent interest. Along the way, we define several further special families of GC-T3O's.

We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular, we compare it to other systems of orientations on triples that satisfy a so-called interiority condition: $\circlearrowleft(ABD)=~\circlearrowleft(BCD)=~\circlearrowleft(CAD)=1$ imply $\circlearrowleft(ABC)=1$ for any $A,B,C,D$. We call such an orientation a P3O (partial 3-order), a natural generalization of a poset, that has several interesting special cases. For example, the order type of a planar point set (that can have collinear triples) is a P3O; we denote a P3O realizable by points as p-P3O. If we do not allow $\circlearrowleft(ABC)=0$, we obtain a T3O (total 3-order). Contrary to linear orders, a T3O can have a rich structure. A T3O realizable by points, a p-T3O, is the order type of a point set in general position. Despite these similarities to order types, P3O and p-T3O that can arise from the orientation of pairwise intersecting convex sets, denoted by C-P3O and C-T3O, turn out to be quite different from order types: there is no containment relation among the family of all C-P3O's and the family of all p-P3O's, or among the families of C-T3O's and p-T3O's. Finally, we study properties of these orientations if we also require that the family of underlying convex sets satisfies the (4,3) property.

We prove that for any planar convex body C there is a positive integer m with the property that any finite point set P in the plane can be three-colored such that there is no translate of C containing at least m points of P, all of the same color. As a part of the proof, we show a strengthening of the Erd\H{o}s-Sands-Sauer-Woodrow conjecture. Surprisingly, the proof also relies on the two dimensional case of the Illumination conjecture.

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 $\Omega(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 $\Theta(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.

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^{\Omega(\sqrt{n}\log n)}$ and $2^{O(n\log\log n/\log n)}$.

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 $\Omega(\log n)$ colors are sometimes necessary. We improve their upper bound to $O(\log^2 n)$.

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., Comment: Updated version, with minor improvements. 8 pages, 1 figure

We improve the upper bound for the maximum possible number of stable matchings among $n$ jobs and $n$ applicants from $131072^n+O(1)$ to $3.55^n+O(1)$. To establish this bound, we state a novel formulation of a certain entropy bound that is easy to apply and may be of independent interest in counting other combinatorial objects, Comment: Version v1 is full of mistakes

Dang et al. have given an algorithm that can find a Tarski fixed point in a $k$-dimensional lattice of width $n$ using $O(\log^{k} n)$ queries. Multiple authors have conjectured that this algorithm is optimal [Dang et al., Etessami et al.], and indeed this has been proven for two-dimensional instances [Etessami et al.]. We show that these conjectures are false in dimension three or higher by giving an $O(\log^2 n)$ query algorithm for the three-dimensional Tarski problem. We also give a new decomposition theorem for $k$-dimensional Tarski problems which, in combination with our new algorithm for three dimensions, gives an $O(\log^{2 \lceil k/3 \rceil} n)$ query algorithm for the $k$-dimensional problem.

We prove that the number of unit distances among $n$ planar points is at most $1.94\cdot n^{4/3}$, improving on the previous best bound of $8n^{4/3}$. We also give better upper and lower bounds for several small values of $n$. We also prove some variants of the crossing lemma and improve some constant factors.

We study the algorithmic problem of computing drawings of graphs in which $(i)$ each vertex is a disk with fixed radius $\rho$, $(ii)$ each edge is a straight-line segment connecting the centers of the two disks representing its end-vertices, $(iii)$ no two disks intersect, and $(iv)$ the distance between an edge segment and the center of a non-incident disk, called \emph{edge-vertex resolution}, is at least $\rho$. We call such drawings \emph{disk-link drawings}. In this paper we focus on the case of constant edge-vertex resolution, namely $\rho=\frac{1}{2}$ (i.e., disks of unit diameter). We prove that star graphs, which trivially admit straight-line drawings in linear area, require quadratic area in any such disk-link drawing. On the positive side, we present constructive techniques that yield improved upper bounds for the area requirements of disk-link drawings for several (planar and nonplanar) graph classes, including bounded bandwidth, complete, and planar graphs. In particular, the presented bounds for complete and planar graphs are asymptotically tight.

We prove a query complexity variant of the weak polynomial Freiman-Ruzsa conjecture in the following form. For any $\epsilon > 0$, a set $A \subset \mathbb{Z}^d$ with doubling $K$ has a subset of size at least $K^{-\frac{4}{\epsilon}}|A|$ with coordinate query complexity at most $\epsilon \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., Comment: Restructured the paper for a more coherent exposition and extended the proofs

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., Comment: Added appendix to v3 from v1, as it was accidentally missing from v2

In this paper we initiate a systematic study of the Tur\'an problem for edge-ordered graphs. A simple graph is called $\textit{edge-ordered}$, if its edges are linearly ordered. An isomorphism between edge-ordered graphs must respect the edge-order. A subgraph of an edge-ordered graph is itself an edge-ordered graph with the induced edge-order. We say that an edge-ordered graph $G$ $\textit{avoids}$ another edge-ordered graph $H$, if no subgraph of $G$ is isomorphic to $H$. The $\textit{Tur\'an number}$ of an edge-ordered graph $H$ is the maximum number of edges in an edge-ordered graph on $n$ vertices that avoids $H$. We study this problem in general, and establish an Erd\H{o}s-Stone-Simonovits-type theorem for edge-ordered graphs -- we discover that the relevant parameter for the Tur\'an number of an edge-ordered graph is its $\textit{order chromatic number}$. We establish several important properties of this parameter. We also study Tur\'an numbers of edge-ordered paths, star forests and the cycle of length four. We make strong connections to Davenport-Schinzel theory, the theory of forbidden submatrices, and show an application in Discrete Geometry., Comment: 41 pages. Updated grants

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$.

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 $\chi(\R^2)\geq 5$.

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$., Comment: Comments are welcome at: https://wordpress.com/post/domotorp.wordpress.com/762

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^{\Omega(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^{\Omega(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|^{\Omega(1)}$ for the aforementioned problem as well (when $d$ is large).

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

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., Comment: 19 pages

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$.

What is the minimum number of colors that always suffice to color every planar set of points such that any disk that contains enough points contains two points of different colors? It is known that the answer to this question is either three or four. We show that three colors always suffice if the condition must be satisfied only by disks that contain a fixed point. Our result also holds, and is even tight, when instead of disks we consider their topological generalization, namely pseudo-disks, with a non-empty intersection. Our solution uses the equivalence that a hypergraph can be realized by stabbed pseudo-disks if and only if it is ABAB-free. These hypergraphs are defined in a purely abstract, combinatorial way and our proof that they are 3-chromatic is also combinatorial.

Suppose that some polynomial $f$ with rational coefficients takes only natural values at natural numbers, i.e., $L=\{f(n)\mid n\in \mathbb N\}\subset\mathbb N$. We show that the base-$q$ representation of $L$ is a context-free language if and only if $f$ is linear, answering a question of Shallit. The proof is based on a new criterion for context-freeness, which is a combination of the Interchange lemma and a generalization of the Pumping lemma., Comment: This paper should be assigned to cs.FL, but I'm not endorsed over there

In this note we disprove a conjecture of Kuzmin and Warmuth claiming that every family whose VC-dimension is at most d admits an unlabeled compression scheme to a sample of size at most d. We also study the unlabeled compression schemes of the joins of some families and conjecture that these give a larger gap between the VC-dimension and the size of the smallest unlabeled compression scheme for them.

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.

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.

In this note we study the complexity of some generalizations of the notion of $st$-numbering. Suppose that given some functions $f$ and $g$, we want to order the vertices of a graph such that every vertex $v$ is preceded by at least $f(v)$ of its neighbors and succeeded by at least $g(v)$ of its neighbors. We prove that this problem is solvable in polynomial time if $fg\equiv 0$, but it becomes NP-complete for $f\equiv g \equiv 2$. This answers a question of the first author posed in 2009.