Geometric combinatorics

Geometric combinatorics studies discrete aspects of geometric objects and uses combinatorial methods to prove geometric inequalities.

A Euclidean body is a nonempty bounded measurable subset of ${\mathbb{R}}^n$ of positive Lebesgue measure. Projection inequalities are unchanged by modifying a body on a set of measure zero; geometric equality statements commonly impose additional regularity.

An axis-parallel box in ${\mathbb{R}}^n$ is a Cartesian product $I_1\times \cdots \times I_n$ of bounded intervals. Its volume is the product of its side lengths, and each coordinate projection is the product of the corresponding intervals.

For $A\subseteq [n]$, the coordinate projection $S_A$ of $S\subseteq {\mathbb{R}}^n$ consists of the coordinate tuples $(x_i{)}_{i\in A}$ obtained from points $x\in S$. Its measure is denoted $|S_A|$.

A multiset $\mathcal{C}$ of subsets of $[n]$ is a $k$-uniform cover when every index belongs to exactly $k$ members of $\mathcal{C}$, counted with multiplicity.

If $\mathcal{C}$ is a $k$-uniform cover of $[n]$ and $S\subseteq {\mathbb{R}}^n$ is a Euclidean body, thenSlicing in one coordinate, applying the theorem inductively to each slice, and then applying Hölder's inequality to the $k$ projected slice functions proves the inequality.

For every Euclidean body $S\subseteq {\mathbb{R}}^n$, there is an axis-parallel box $B$ such thatThe proof minimizes an array of candidate projection volumes subject to the finitely many inequalities from irreducible uniform covers. Tight constraints force the array to factor into its singleton coordinates, which become the side lengths of $B$.

The sets $[n]\setminus \{i\}$ form an $(n-1)$-uniform cover, so the uniform covers theorem gives

Equality in the three-dimensional Loomis--Whitney inequality forces a measurable body to agree up to a null set with a Cartesian product $E_1\times E_2\times E_3$. This follows from the equality conditions in the two Cauchy-Schwarz inequalities used in its proof. If the body is connected and is a finite union of positive-volume axis-parallel boxes, each $E_i$ is an interval and equality up to a null set upgrades to exact equality with one box.

A uniform cover is irreducible when it is not the disjoint union, as a multiset, of two nonempty uniform covers. There are only finitely many irreducible uniform covers of a fixed finite set: their multiplicity vectors form an antichain in ${\mathbb{N}}^{2^n}$, and Dickson lemma forbids an infinite antichain there.

Every subset of ${\mathbb{N}}^d$ has finitely many coordinatewise minimal elements. Equivalently, ${\mathbb{N}}^d$ has no infinite antichain in its coordinatewise partial order.