In 1964, ErdH{o}s, Hajnal and Moon introduced a saturation version of Turans classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in a $K_r$-free, $n$-vertex graph with the property that the addition
of any further edge yields a copy of $K_r$. We consider analogues of this problem in other settings. We prove a saturation version of the ErdH{o}s-Szekeres theorem about monotone subsequences and saturati
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, Martin, Masa{v{r}}{i}k, Shull, Smith, Uzzell, and Wang (Europ. J. Comb. 2020), namely: - What is the local complete bipartite cover number of a difference graph? - Is there a sequence of graphs with constant local difference graph cover number and unbounded local complete bipartite cover number? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim emph{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_2log_2 n$. We conclude with some remarks on covering numbers for digraphs and Ferrers dimension.
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 1s 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-65le 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.
A widely investigated subject in combinatorial geometry, originated from ErdH{o}s, is the following. Given a point set $P$ of cardinality $n$ in the plane, how can we describe the distribution of the determined distances? This has been generalized in
many directions. In this paper we propose the following variants. Consider planar arrangements of $n$ lines. Determine the maximum number of triangles of unit area, maximum area or minimum area, determined by these lines. Determine the minimum size of a subset of these $n$ lines so that all triples determine distinct area triangles. We prove that the order of magnitude for the maximum occurrence of unit areas lies between $Omega(n^2)$ and $O(n^{9/4})$. This result is strongly connected to both additive combinatorial results and Szemeredi--Trotter type incidence theorems. Next we show a tight bound for the maximum number of minimum area triangles. Finally we present lower and upper bounds for the maximum area and distinct area problems by combining algebraic, geometric and combinatorial techniques.
