According to a conjecture of Pach, there are O(n) tangent pairs among any family of n Jordan arcs in which every pair of arcs has precisely one common point and no three arcs share a common point. This conjecture was proved for two special cases, however, for the general case the currently best upper bound is only O(n^{7/4}). This is also the best known bound on the number of tangencies in the relaxed case where every pair of arcs has at most one common point. We improve the bounds for the latter and former cases to O(n^{5/3}) and O(n^{3/2}), respectively. We also consider a few other variants of these questions, for example, we show that if the arcs are x-monotone, each pair intersects at most once and their left endpoints lie on a common vertical line, then the maximum number of tangencies is Θ(n^{4/3}). Without this last condition the number of tangencies is O(n^{4/3}(log n)^{1/3}), improving a previous bound of Pach and Sharir. Along the way we prove a graph-theoretic theorem which extends a result of Erdős and Simonovits and may be of independent interest.

We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant ε ∈ (0,1), one could construct a (2 + ε )-spanner with O (n log(n )) edges (SICOMP 2019), and there is a lower bound of Ω(n2) edges for any (2 — ε )-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 Ω(n log n ) edges, and for stretch 2 + ε for any fixed ε ∈ (0,1), O (n ) edges are sufficient. Our lower bound is the first super-linear lower bound for stretch 2.

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.

A long-standing open conjecture of Branko Grünbaum from 1972 states that any arrangement of n pairwise intersecting pseudocircles in the plane can have at most 2n-2 digons. Agarwal et al. proved this conjecture for arrangements in which there is a common point surrounded by all pseudocircles. Recently, Felsner, Roch and Scheucher showed that Grünbaum’s conjecture is true for arrangements of pseudocircles in which there are three pseudocircles every pair of which creates a digon. In this paper we prove this over 50-year-old conjecture of Grünbaum for any arrangement of pairwise intersecting circles in the plane.

We study exak(n,F), the largest number of edges in an n-vertex graph that contains exactly k copies of a given subgraph F. The case k=0 is the Turán number ex(n,F) that is among the most studied parameters in extremal graph theory. We show that for any F and k, exak(n,F)=(1+o(1))ex(n,F) and determine the exact values of exak(n,K3) and exa1(n,Kr) 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 n2−exa1(n,F). Among other results we show that the number of queries that were answered NO is at least n2−exa1(n,F).

Abstract. Recently, the saturation problem of 0-1 matrices has gained a lot of attention. This problem can be regarded as a saturation problem of ordered bipartite graphs. Motivated by this, we initiate the study of the saturation problem of ordered and cyclically ordered graphs. We prove that dichotomy also holds in these two cases, i.e., for a (cyclically) ordered graph its saturation function is either bounded or linear. We also determine the order of magnitude for large classes of (cyclically) ordered graphs, giving infinitely many examples exhibiting both possible behaviors, answering a problem of Pálvölgyi. In particular, in the ordered case we define a natural subclass of ordered matchings, the class of linked matchings, and we start their systematic study, concentrating on linked matchings with at most three links and prove that many of them have bounded saturation function. In both the ordered and cyclically ordered case we also consider the semisaturation problem, where dichotomy holds as well and we can even fully characterize the graphs that have bounded semisaturation function.

Abstract What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even: If both m and n are even, then every pair of sides may cross and so the answer is mn. If exactly one polygon, say the n-gon, has an odd number of sides, it can intersect each side of the m-gon polygon at most $$n-1$$ n - 1 times; hence there are at most $$mn-m$$ m n - m intersections. It is not hard to construct examples that meet these bounds. If both m and n are odd, the best known construction has $$mn-(m+n)+3$$ m n - ( m + n ) + 3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only $$mn-(m + \lceil {n}/{6} \rceil )$$ m n - ( m + ⌈ n / 6 ⌉ ) , for $$m \ge n$$ m ≥ n . We prove a new upper bound of $$mn-(m+n)+C$$ m n - ( m + n ) + C for some constant C, which is optimal apart from the value of C.

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(Kn)=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)≤m(G)≤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≤m(T)≤n−2. Our proof uses results about the weighted version of the problem for Kn, which may be of independent interest. We also exhibit a sequence Gn of graphs with m(Gn)=n−b(n) such that Gn has O(nb(n)) edges and n vertices.

We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite graphs. In particular, we show that in every cover of a Young diagram with $\binom{2k}{k}$ steps with generalized rectangles, there is a row or a column in the diagram that is used by at least $k+1$ rectangles and prove that this is best possible. This answers two questions by Kim et al. [ European J. Combin., 86 (2020), 103074], namely, what is the local complete bipartite covering number of a difference graph, and is there a sequence of graphs with a constant local difference graph covering numbers and unbounded local complete bipartite covering numbers? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim et al., we use the results on local covering numbers to provide lower and upper bounds for the local dimension of partially ordered sets of height 2. We discuss the local dimension of some posets related to Boolean lattices and show that the poset induced by the first two layers of the Boolean lattice has local dimension $(1 + o(1))\log_2\log_2 n$. We conclude with some remarks on covering numbers for digraphs and Ferrers dimension.

A 0-1 matrix $M$ is saturating for a 0-1 matrix $P$ if $M$ does not contain a submatrix that can be turned into $P$ by changing some 1 entries to 0 entries, and changing an arbitrary 0 to 1 in $M$ introduces such a submatrix in $M$. In saturation problems for 0-1 matrices we are interested in estimating the minimum number of 1 entries in an $m \times n$ matrix that is saturating for $P$, in terms of $m$ and $n$. In other words, we wish to give good estimates for the saturation function of $P$. Recently, Brualdi and Cao [R. A. Brualdi and L. Cao, preprint, arXiv:2005.00379, 2020] initiated the study of saturation problems in the context of 0-1 matrices. We extend their work in several directions. We prove that every 0-1 forbidden matrix has its saturation function either in $\Theta(1)$ or $\Theta(n)$ in the case when we restrict ourselves to square saturating matrices. Then we give a partial answer to a question posed by Brualdi and Cao about the saturation function of $J_k$, which is obtained from the identity matrix $I_k$ by putting the first row after the last row. Furthermore, we exhibit a $5\times 5$ permutation matrix with the saturation function bounded from the above by a fixed constant. We complement this result by identifying large classes of 0-1 matrices with linear saturation function. Finally, we completely resolve the related semisaturation problem as far as the constant versus linear dichotomy is concerned.

What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even. If both m and n are odd, the best known construction has mn-(m+n)+3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only mn-(m + ⌈ n/6 ⌉), for m ≥ n. We prove a new upper bound of mn-(m+n)+C for some constant C, which is optimal apart from the value of C.

We prove that it is always possible to color online nonrepetitively any (partial) k-tree (that is, graphs with tree-width at most k) with 4k colors. This implies that it is always possible to color online nonrepetitively cycles, trees and series-parallel graphs with 16 colors. Our results generalize the respective (offline) nonrepetitive coloring results.

Abstract We prove that the intersection hypergraph of a family of n pseudo-disks with respect to another family of pseudo-disks admits a proper coloring with four colors and a conflict-free coloring with $$O(\log n)$$ O ( log n ) colors. Along the way we prove that the respective Delaunay-graph is planar. We also prove that the intersection hypergraph of a family of n regions with linear union complexity with respect to a family of pseudo-disks admits a proper coloring with constantly many colors and a conflict-free coloring with $$O(\log n)$$ O ( log n ) colors. Our results serve as a common generalization and strengthening of many earlier results, including ones about proper and conflict-free coloring points with respect to pseudo-disks, coloring regions of linear union complexity with respect to points and coloring disks with respect to disks.

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

We study whether for a given planar family $${\mathcal {F}}$$ there is an m such that any finite set of points can be 3-colored so that any member of $${\mathcal {F}}$$ that contains at least m points contains two points with different colors. We conjecture that if $${\mathcal {F}}$$ is a family of pseudo-disks, then such an m exists. We prove this in the special case when $${\mathcal {F}}$$ is the family of all homothetic copies of a given convex polygon. We also study the problem in higher dimensions.

We study combinatorial parameters of a recently introduced bootstrap percolation problem in finite projective planes. We present sharp results on the size of the minimum percolating sets and the maximal nonpercolating sets. Additional results on the minimal and maximal percolation time as well as on the critical probability in the projective plane are also presented.

Let $L$ be a set of positive integers. We call a (directed) graph $G$ an $L$ -cycle graph if all cycle lengths in $G$ belong to $L$. Let $c(L,n)$ be the maximum number of cycles possible in an $n$-vertex $L$-cycle graph (we use $\vec{c}(L,n)$ for the number of cycles in directed graphs). In the undirected case we show that for any fixed set $L$, we have $c(L,n)=\Theta(n^{\lfloor k/\ell \rfloor})$, where $k$ is the largest element of $L$ and $2\ell$ is the smallest even element of $L$ (if $L$ contains only odd elements, then $c(L,n)=\Theta(n)$ holds). We also give a characterization of $L$-cycle graphs when $L$ is a single element. In the directed case we prove that for any fixed set $L$, we have $\vec{c}(L,n)=(1+o(1))(\frac{n-1}{k-1})^{k-1}$, where $k$ is the largest element of $L$. We determine the exact value of $\vec{c}(\{k\},n)$ for every $k$ and characterize all graphs attaining this maximum.

We consider the problem of 2-coloring geometric hypergraphs. Specifically, we show that there is a constant m such that any finite set of points in the plane $${\mathcal {S}} \subset {\mathbb {R}}^2$$ can be 2-colored such that every axis-parallel square that contains at least m points from $${\mathcal {S}}$$ contains points of both colors. Our proof is constructive, that is, it provides a polynomial-time algorithm for obtaining such a 2-coloring. By affine transformations this result immediately applies also when considering 2-coloring points with respect to homothets of a fixed parallelogram.

We prove that if an $n$-vertex graph $G$ can be drawn in the plane such that each pair of crossing edges is independent and there is a crossing-free edge that connects their endpoints, then $G$ has $O(n)$ edges. Graphs that admit such drawings are related to quasi-planar graphs and to maximal $1$-planar and fan-planar graphs.

We investigate the relationship between two kinds of vertex colorings of hypergraphs: unique-maximum (UM) colorings and conflict-free (CF) colorings. In a UM coloring, the colors are ordered, and in every hyperedge of the hypergraph the maximum color in the hyperedge occurs in only one vertex of the hyperedge. In a CF coloring, in every hyperedge of the hypergraph there exists a color in the hyperedge that occurs in only one vertex of the hyperedge. We consider the corresponding UM and CF chromatic numbers and investigate their relationship in arbitrary hypergraphs. Then, we concentrate on hypergraphs that are induced by simple paths in tree graphs.

We settle a problem of Dujmović, Eppstein, Suderman, and Wood by showing that there exists a function $f$ with the property that every planar graph $G$ with maximum degree $d$ admits a drawing with noncrossing straight-line edges, using at most $f(d)$ different slopes. If we allow the edges to be represented by polygonal paths with one bend, then $2d$ slopes suffice. Allowing two bends per edge, every planar graph with maximum degree $d\ge 3$ can be drawn using segments of at most $\lceil d/2\rceil$ different slopes. There is only one exception: the graph formed by the edges of an octahedron is 4-regular, yet it requires 3 slopes. Every other planar graph requires exactly $\lceil d/2\rceil$ slopes.