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.

In this paper, we consider saturation problems related to the celebrated Erdős--Szekeres convex polygon problem. For each $n \ge 7$, we construct a planar point set of size $(7/8) \cdot 2^{n-2}$ which is saturated for convex $n$-gons. That is, the set contains no $n$ points in convex position while the addition of any new point creates such a configuration. This demonstrates that the saturation number is smaller than the Ramsey number for the Erdős--Szekeres problem. The proof also shows that the original Erdős--Szekeres construction is indeed saturated. Our construction is based on a similar improvement for the saturation version of the cups-versus-caps theorem. Moreover, we consider the generalization of the cups-versus-caps theorem to monotone paths in ordered hypergraphs. In contrast to the geometric setting, we show that this abstract saturation number is always equal to the corresponding Ramsey number.

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.

Abstract An odd wheel graph is a graph formed by connecting a new vertex to all vertices of an odd cycle. We answer a question of Rosenfeld and Le by showing that odd wheels cannot be drawn in the plane so that the lengths of the edges are odd integers.