Let d and k be integers with $$1 \le k \le d-1$$ . Let $$\Lambda $$ be a d-dimensional lattice and let K be a d-dimensional compact convex body symmetric about the origin. We provide estimates for the minimum number of k-dimensional linear subspaces needed to cover all points in $$\Lambda \cap K$$ . In particular, our results imply that the minimum number of k-dimensional linear subspaces needed to cover the d-dimensional $$n \times \cdots \times n$$ grid is at least $$\Omega \bigl (n^{d(d-k)/(d-1)-\varepsilon }\bigr )$$ and at most $$O\bigl (n^{d(d-k)/(d-1)}\bigr )$$ , where $$\varepsilon >0$$ is an arbitrarily small constant. This nearly settles a problem mentioned in the book by Brass et al. (Research problems in discrete geometry, Springer, New York, 2005). We also find tight bounds for the minimum number of k-dimensional affine subspaces needed to cover $$\Lambda \cap K$$ . We use these new results to improve the best known lower bound for the maximum number of point–hyperplane incidences by Brass and Knauer (Comput Geom 25(1–2):13–20, 2003). For $$d \ge 3$$ and $$\varepsilon \in (0,1)$$ , we show that there is an integer $$r=r(d,\varepsilon )$$ such that for all positive integers n, m the following statement is true. There is a set of n points in $$\mathbb {R}^d$$ and an arrangement of m hyperplanes in $$\mathbb {R}^d$$ with no $$K_{r,r}$$ in their incidence graph and with at least $$\Omega \bigl ((mn)^{1-(2d+3)/((d+2)(d+3)) - \varepsilon }\bigr )$$ incidences if d is odd and $$\Omega \bigl ((mn)^{1-(2d^2+d-2)/((d+2)(d^2+2d-2)) -\varepsilon }\bigr )$$ incidences if d is even.

A binary matrix is a matrix with entries from the set {0,1}. We say that a binary matrix A contains a binary matrix S if S can be obtained from A by removal of some rows, some columns, and changing some 1-entries to 0-entries. If A does not contain S, we say that A avoids S. A k-permutation matrix P is a binary k χ k matrix with exactly one 1-entry in every row and one 1-entry in every column. The Füredi-Hajnal conjecture, proved by Marcus and Tardos, states that for every permutation matrix P, there is a constant cp such that for every n ∊ ℕ, every n × n binary matrix A with at least cpn 1-entries contains P. We show that cp ≤ 2O(κ2/3 log7/3 k/(log log κ)1/3) asymptotically almost surely for a random k-permutation matrix P. We also show that cp < 2(4+o(1))k for every k- permutation matrix P, improving the constant in the exponent of a recent upper bound on cp by Fox. We also consider a higher-dimensional generalization of the Stanley-Wilf conjecture about the number of d-dimensional n-permutation matrices avoiding a fixed d-dimensional k-permutation matrix, and prove almost matching upper and lower bounds of the form (2k)O(n) · (n!)d-1-1/(d-1) and n−O(k)kΩ(n) · (n!)d-1-1/(d-1), respectively.

We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon $P$ with $n$ vertices. We give a randomized near-linear-time $(1-\varepsilon)$-approximation algorithm for this problem: in $O(n( \log^2 n + (1/\varepsilon^3) \log n + 1/\varepsilon^4))$ time we find a convex polygon contained in $P$ that, with probability at least $2/3$, has area at least $(1-\varepsilon)$ times the area of an optimal solution. We also obtain similar results for the variant of computing a convex polygon inside $P$ with maximum perimeter. To achieve these results we provide new results in geometric probability. The first result is a bound relating the area of the largest convex body inside $P$ to the probability that two points chosen uniformly at random inside $P$ are mutually visible. The second result is a bound on the expected value of the difference between the perimeter of any planar convex body $K$ and the perimeter of the convex hull of a uniform random sample inside $K$.

We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon P with n vertices. We give a randomized near-linear-time (1 − ϵ)-approximation algorithm for this problem: in O((n/ϵ6) log2 n log(1/δ)) time we find a convex polygon contained in P that, with probability at least 1 − δ, has area at least (1 − ϵ) times the area of an optimal solution.

Motivated by recent papers of Eppstein, Abel et al. and Barat et al., and by a question of Wood, we investigate properties of planar point sets with no 5-hole (no empty convex pentagon). We answer a question of Wood by showing that the visibility graph of a finite point set with no 5-hole may contain a clique of arbitrary size. This is in contrast with the previous examples of sets with no 5-hole, including the example of the (finite) square lattice. In our construction we use several equivalent local characterizations of (locally) finite planar point sets with no 5-hole which may be of independent interest. Our construction relies on a construction scheme which allows to derive new, non-trivial examples of sets with no 5-hole.

Two words have a reverse if they have the same pair of distinct letters on the same pair of positions, but in reversed order. A set of words no two of which have a reverse is said to be reverse-free. Let $F(n,k)$ be the maximum size of a reverse-free set of words from $[n]^k$, where no letter repeats within a word. We show the following lower and upper bounds in the case $n \ge k$: $F(n,k) \in n^k k^{-k/2 + O(k /\log k)}$. As a consequence of the lower bound, a set of $n$-permutations, each two having a reverse, has size at most $n^{n/2 + O (n/\log n)}$.

The VC-dimension of a family P of n-permutations is the largest integer k such that the set of restrictions of the permutations in P on some k-tuple of positions is the set of all k! permutation patterns. Let rk(n) be the maximum size of a set of n-permutations with VC-dimension k. Raz showed that r2(n) grows exponentially in n. We show that and for every t ≥ 1, we have and . We also study the maximum number pk(n) of 1-entries in an n × n (0, 1)-matrix with no (k + 1)-tuple of columns containing all (k + 1)-permutation matrices. We determine that p3(n) = Θ(nα(n)) and for every t ≥ 1. We also show that for every positive s there is a slowly growing function ζs(m) (for example for every odd s ≥ 5) satisfying the following. For all positive integers m, n, B and every m × n (0, 1)-matrix M with ζs(m)Bn 1-entries, the rows of M can be partitioned into s intervals so that some ⌊Bn/m⌋-tuple of columns contains at least B 1-entries in each of the intervals.