If a finitely generated Coxeter group $W$ is finite, its integer-valued Coxeter length has a maximum. Conversely, if some $w_0$ has globally maximal length $N$, every group element has a word of length at most $N$. There are only finitely many words of bounded length in the finite set of simple generators, so $W$ is finite.

Realize the finite group as the reflection group of a root system with fundamental system $\Delta$ and positive system $\Pi$. Maximality and the fact that multiplication by a simple generator changes Coxeter length by one giveThe positive-root criterion for Coxeter length therefore gives $w_0\Delta \subseteq -\Pi$. Since $w_0\Delta$ is itself fundamental, it must be the simple system $-\Delta$ of the positive system $-\Pi$.

If $v_0$ is another maximal-length element, the same argument gives $v_0\Delta =-\Delta =w_0\Delta$. Hence $v_0^{-1}{w}_0$ stabilizes $\Delta$, and part c gives $v_0^{-1}{w}_0=1$. The longest element of a finite Coxeter group is therefore unique.

Use the positive-root criterion for Coxeter length: for a simple root $\alpha \in \Delta$,The hypothesis $w\Delta \subseteq \Pi$ therefore says that every simple generator is a right ascent of $w$. If $w\ne 1$, a reduced expression in a Coxeter group for $w$ has a final simple generator $s_{\alpha }$, and deleting it givesa contradiction. Hence $w=1$.

If $w$ stabilizes $\Delta$ setwise, then $w\Delta =\Delta \subseteq \Pi$, so the result just proved gives $w=1$. Thus the stabilizer of every fundamental system is trivial.

The reflection group of a root system isEvery generating reflection permutes $\Phi$, so every $w\in W(\Phi )$ does too. If $\Delta$ is fundamental, then $w\Delta$ is a basis contained in $\Phi$. Writingshows thatthe coefficients are unchanged and therefore still have one sign. Thus $w\Delta$ is another fundamental system, and $W(\Phi )$ acts on the set of all fundamental systems.

A root system in the real inner product space $V$ is a finite spanning set $\Phi \subset V\setminus \{0\}$ such thatwhere the orthogonal reflectionFor a crystallographic root system one additionally requires $2(\beta ,\alpha )/(\alpha ,\alpha )\in \mathbb{Z}$; that condition is not needed for general finite reflection groups.

A fundamental system of a root system is a basis $\Delta \subset \Phi$ such that every root has either all nonnegative or all nonpositive coordinates in this basis. Its associated positive system of a root system isand $\Phi =\Pi \bigsqcup (-\Pi )$.

Let $D>0$ be the diameter of the bounded set $S$, and choose $x_0\in S$. Then $S\subseteq B(x_0,D)$. It is enough to prove a volumetric covering bound for the unit ball.

Choose a maximal $1/4$-separated set $N$ in $B(0,1)$. The balls of radius $1/8$ centred at points of $N$ are disjoint and lie in $B(0,9/8)$. Comparing volumes givesMaximality means that the balls of radius $1/4$ centred at $N$ cover the unit ball.

After translating and scaling, at most $9^n$ balls of radius $D/4$ cover $S$. Assign each point of $S$ to one covering ball containing it. This gives at most $9^n$ disjoint pieces, each of diameter at most $D/2<D$. Thus the claim holds with the absolute constant $C=9$.

The Borsuk conjecture asserted that every bounded subset of ${\mathbb{R}}^d$ of positive diameter can be partitioned into $d+1$ subsets of strictly smaller diameter. We construct a Kahn-Kalai counterexample to the Borsuk conjecture.

For every $2p$-subset $A$ of $[4p]$, let $v_A\in \{-1,1{\}}^{4p}$ be $1$ on $A$ and $-1$ outside it, and defineBecause $x_A=x_{A^c}$, retain one representative of each complementary pair. The resulting set $X$ has $\frac{1}{2}\left(\genfrac{}{}{0ex}{}{4p}{2p}\right)$ points. For $s=|A\cap B|$,andAll $x_A$ have the same norm, so their distance is largest exactly when this inner product is smallest, namely when $s=p$.

Every smaller-diameter part of $X$ therefore corresponds to a family with no pair having intersection $p$. Part ii bounds such a part by $2\left(\genfrac{}{}{0ex}{}{4p}{p-1}\right)$. Any smaller-diameter partition consequently needs at leastparts. By Stirling formula, this ratio grows like $(27/16{)}^p$ up to a polynomial factor, whereas $d+1=O(p^2)$. For every sufficiently large prime $p$, the required number of parts exceeds $d+1$, disproving the conjecture.

Partition the family into complementary pairs $\{A,[4p]\setminus A\}$. Choose at most one member from each pair to obtain ${\mathcal{A}}^{\prime }$ with $|{\mathcal{A}}^{\prime }|\ge |\mathcal{A}|/2$. Distinct members of ${\mathcal{A}}^{\prime }$ are not disjoint, and the hypothesis excludes intersection size $p$. Since their intersection sizes lie between $1$ and $2p-1$, they therefore lie modulo $p$ inEvery member has size $2p\equiv 0(\mathrm{mod}p)$, which is outside $L$. The Frankl-Wilson theorem givesand hence

One uniform form of the Frankl-Wilson theorem is as follows. Let $p$ be prime and let $L\subseteq {\mathbb{F}}_p$ have $s\le \min \{k,n-k\}$ elements. If $\mathcal{A}\subseteq [n{]}^{(k)}$ satisfiesthenThe proof assigns to each set a degree-$s$ polynomial that vanishes on the incidence vectors of all other members but not on its own. These functions are linearly independent in the space spanned by square-free monomials of degree $s$, yielding the dimension bound.

Apply coordinate compression in a product of paths in both coordinates. Replacing every fiber by an initial interval preserves the number of edges inside that fiber; between two neighboring fibers, the compressed sets span the minimum of their sizes, at least their original intersection size. Repeating the operation therefore never decreases the number of edges spanned and eventually produces a down-set.

Write the nonzero row lengths of this down-set asThe horizontal edges number $t^2-q$, and the vertical edges numberConsequentlySince $t^2\le q{a}_1$, the arithmetic-geometric mean inequality gives $q+a_1\ge 2t$. Henceas required.

False. In the grid graph $[9{]}^2$, take the four-row stripIt has $36=6^2$ vertices, and only the nine edges between rows four and five lie in its edge boundary. The corner square $[6{]}^2$ has six boundary edges along each of its two exposed sides, for a total of twelve. Thus a set of size $t^2$ can have smaller edge boundary than $[t{]}^2$.

For $\mathcal{A}$ in the $n$-dimensional Boolean hypercube, the edge-isoperimetric inequality in the discrete cube iswhere $e(\mathcal{A})$ is the number of edges spanned by $\mathcal{A}$. Since the cube is $n$-regular, the equivalent boundary form is

We prove the induced-edge form by induction on $n$. Split the cube according to its last coordinate, and let the two sections have sizes $a\ge b$. At most $b$ edges of $\mathcal{A}$ cross between the sections. The induction hypothesis givesPut $x=b/(a+b)\le 1/2$. The required comparison with $\frac{1}{2}(a+b){\log }_2(a+b)$ is equivalent towhere $H_2$ is the binary entropy function. This follows from concavity because the graph of $H_2$ lies above the chord joining $(0,0)$ to $(1/2,1)$. The induction is complete. Subcubes attain equality when $|\mathcal{A}|$ is a power of two.

Fix a prime number $p>r$. Distinct members of an intersecting $r$-uniform family have intersection size inwhereas every member has size $r\notin L$ modulo $p$. The Frankl-Wilson theorem with $|L|=r-1$ therefore givesFor fixed $r$,This is the asserted asymptotic weakening of the Erdős-Ko-Rado theorem.

No. Let $n=7$, $r=3$, take $\mathcal{A}=\{\{1,2,3\}\}$, and letThe families are nonempty and cross-intersecting. There aremembers, so

Suppose $\mathcal{A},\mathcal{B}\subseteq [n{]}^{(r)}$ are cross-intersecting families. The iterated upper shadow ${\nabla }_{n-r}\mathcal{A}$ is disjoint frombecause $A\subseteq [n]\setminus B$ would mean $A\cap B=\varnothing$. HenceIf $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$, the upper-shadow form of the Kruskal-Katona theorem givesIt follows from Pascal's identity that $|\mathcal{B}|<\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$. Thus the two sizes cannot both exceed that number.

The Erdős-Ko-Rado theorem says that if $n\ge 2r$ and $\mathcal{A}\subseteq [n{]}^{(r)}$ is an intersecting family, thenThe star of all $r$-sets containing one fixed point attains equality.

For the shadow proof, let ${\nabla }_{n-r}\mathcal{A}$ be the iterated upper shadow at level $n-r$, and letThese two families are disjoint: if $A\subseteq [n]\setminus B$, then $A$ and $B$ are disjoint. The upper-shadow form of the Kruskal-Katona theorem says that ifthenBut $|{\mathcal{A}}^c|=|\mathcal{A}|$, so disjointness and Pascal's identity would give more thanmembers at level $n-r$, a contradiction.

For the Katona circle method, place $[n]$ in a cyclic order. At most $r$ of its cyclic intervals of length $r$ can belong to an intersecting family. Indeed, after fixing one selected interval, every selected interval starts at one of the $2r-1$ positions at cyclic distance below $r$ from its start; apart from the fixed interval, these positions form $r-1$ pairs whose corresponding intervals are disjoint. Double-count pairs consisting of $A\in \mathcal{A}$ and a cyclic order in which $A$ is consecutive. There are $(n-1)!$ cyclic orders, at most $r$ selected intervals in each, and each $A$ is consecutive in $r!(n-r)!$ cyclic orders. Thereforewhich rearranges to the required bound.

False. Take $n=6$, $r=3$, andThere are $1+3\cdot 3=10$ members. Its lower shadow consists of the three pairs inside $\{1,2,3\}$ and the nine pairs having one point there and one in $\{4,5,6\}$, so $|\partial \mathcal{A}|=12$. Its upper shadow consists of the twelve four-sets containing at least two points of $\{1,2,3\}$, so $|\nabla \mathcal{A}|=12$. The sum is $24$.

The initial lex segment of length ten is the star of all triples containing $1$; its lower and upper shadows have sizes $15$ and $10$. The initial colex segment consists of all triples in $[5]$; its lower and upper shadows have sizes $10$ and $15$. Both sums are $25$, so neither canonical segment minimizes the sum.

Let $c(A)=[n]\setminus A$ and reverse the order of the ground set by $j\mapsto n+1-j$. The resulting bijection sends lexicographic order on $[n{]}^{(r)}$ to colexicographic order on $[n{]}^{(n-r)}$. It also sends the iterated upper shadow of an $r$-uniform family at level $r+1$ to the lower shadow of the corresponding $(n-r)$-uniform family, up to the same harmless reversal of the ground set.

The Kruskal-Katona theorem says that this lower shadow is smallest for an initial colex segment. Undoing the complement and reversal therefore says that the upper shadow of a family of fixed size in $[n{]}^{(r)}$ is smallest for the initial lex segment.