Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 112 (Probabilistic Combinatorics and Its Applications)

Write ${\lambda }_n$ for Lebesgue measure on ${\mathbb{R}}^n$. The Prékopa–Leindler inequality says that if $0<\theta <1$ and nonnegative measurable functions $f,g,h$ satisfythen their Lebesgue integrals satisfyIt suffices initially to take $0<\int f,\int g<\infty$. Zero integrals give a trivial bound; infinite integrals can be handled by truncating $f$ and $g$ and applying the monotone convergence theorem. As usual, a zero factor makes the asserted lower bound zero.

Here is a one-dimensional proof using quantile functions. Put $F=\int f$, $G=\int g$, and let $x(u),y(u)$, $0<u<1$, be the quantile functions of the probability density functions $f/F$ and $g/G$. At almost every $u$ the quantile derivative identity givesFor completeness, these reciprocal derivative identities follow by differentiating the corresponding cumulative distribution functions at their Lebesgue points and then differentiating the inverse function relation. Sampling a quantile function at a uniform argument samples the density itself, so the exceptional set, including locations where the density vanishes or is infinite, has probability zero. Gaps in a density's support can give jumps in its quantile function; they do not invalidate the argument below.

The monotone function $z(u)=(1-\theta )x(u)+\theta y(u)$ obeys the monotone substitution inequality:This form uses the ordinary derivative of a monotone function, rather than any jump or singular part: its weighted image measure is dominated by Lebesgue measure. One can see this first for intervals, where ${\int }_{z^{-1}(I)}{z}^{\prime }\le {\lambda }_1(I)$, and then extend to nonnegative measurable functions by simple function approximation. Thus no assumption of strictly positive smooth probability density functions is hidden in the proof.

Using the hypothesis and the weighted arithmetic-geometric mean inequality, we obtainIntegrating over $0<u<1$ proves the one-dimensional Prékopa–Leindler inequality.

For higher dimensions, use mathematical induction and Tonelli theorem. Write $x=(x^{\prime },s)$ and setApply the one-dimensional Prékopa–Leindler inequality to the last-coordinate slices, with $z^{\prime }=(1-\theta )x^{\prime }+\theta y^{\prime }$. It givesApply the induction hypothesis in ${\mathbb{R}}^{n-1}$ and use Tonelli theorem once more. For finite total integrals, infinite slice integrals occur only on null sets and may be replaced by zero there; this only weakens the displayed premise. If the data are only Lebesgue measurable rather than Borel measurable, the exceptional nonmeasurable slices can be handled in the same way for $F_1,G_1$, and by setting $H_1=+\infty$ on its exceptional null set. The total integrals are unchanged, and the slice premise holds everywhere it is needed. The result therefore holds for general nonnegative measurable functions.

First take nonempty bounded open sets $A,B\subset {\mathbb{R}}^n$. Their Minkowski sum is open and hence a Lebesgue measurable set. Apply the Prékopa–Leindler inequality to their indicator functions and the indicator function of $(1-\theta )A+\theta B$. This gives the multiplicative formTo obtain the usual additive Brunn–Minkowski inequality, put $a={\lambda }_n(A{)}^{1/n}$, $b={\lambda }_n(B{)}^{1/n}$, $A_0=A/a$ and $B_0=B/b$. Both normalized open sets have Lebesgue measure one. For $\theta =b/(a+b)$,The multiplicative bound and the scaling rule for Lebesgue measure implyReplacing $A,B$ by $A\cap B(0,R),B\cap B(0,R)$ and using continuity from below extends this form of the Brunn–Minkowski inequality to all nonempty open sets, including those of infinite Lebesgue measure. This open-set form is sufficient here and avoids any measurability qualification for sums of arbitrary measurable sets.

No: the Lebesgue measure can decrease when separate components of the Minkowski sum merge. A one-dimensional example is enough to disprove the assertion in general. TakeThe Minkowski sum $A+tB$ consists of four open intervals, with left endpoints $0,10,2t,10+2t$ and common length $(1+t)/10$. At $t=4$ the four open intervals are disjoint, soAt $t=5$ the middle two open intervals coincide and the remaining three are disjoint, soFor a counterexample in any prescribed dimension $n>1$, take Cartesian products of these open sets with $(0,1)$ in the remaining coordinates. Compare $t_2=5$ with $t_1=5-\delta$, where $\delta ={\delta }_n>0$ is sufficiently small, and choose the interval width $\epsilon >0$ so small that $6\epsilon <2\delta$. The four intervals remain disjoint at $t_1$, givingChoosing $(1-\delta /6{)}^n>3/4$ makes the latter smaller. Here $A_n=((0,\epsilon )\cup (10,10+\epsilon ))\times (0,1{)}^{n-1}$ and $B_n=((0,\epsilon )\cup (2,2+\epsilon ))\times (0,1{)}^{n-1}$. The Brunn–Minkowski inequality gives a lower bound at each value of $t$; it does not give the claimed monotonicity for arbitrary open sets.

Normalize the surface area of the spherical cap by writingTwo elementary descriptions of a spherical cap are useful. The spherical polar coordinates formula givesProjecting orthogonally onto the last $n-1$ coordinates givesIndeed, the upper hemisphere is the graph $x_1=\sqrt{1-\Vert x^{\prime }{\Vert }^2}$, whose surface area factor is $(1-\Vert x^{\prime }{\Vert }^2{)}^{-1/2}\le 1/\cos \rho$ on $\Vert x^{\prime }\Vert \le \sin \rho$. This establishes the upper projection bound directly.

Set $F(\rho )={\sin }^n\rho -q(\rho )$. The supplied ratio bound implies $c_n<\sqrt{(n+1)/(2\pi )}/n\le 1/2$ for $n\ge 2$. Consequently, at $\rho =\pi /4$,Also,On $[\pi /4,\pi /2]$, the expression in parentheses is strictly decreasing; it starts positive and ends negative. Thus $F$ first increases and then decreases, so its minimum on this interval is at an endpoint. Since $F(\pi /2)=1/2$, both endpoint values are nonnegative. The spherical cap area upper bound follows:

Use the same normalized spherical cap area $q$, constant $c_n$ and function $F={\sin }^n\rho -q$ as above. Put ${\rho }_0=\arcsin (1/\sqrt{n})$. The supplied ratio estimate givesThe middle inequality holds for every $n\ge 2$, since $n+1\le 2\pi (n-1)$. Applying the upper projection bound for the spherical cap at ${\rho }_0$ yieldsso $F({\rho }_0)\ge 0$.

RecallAt ${\rho }_0$ the expression in parentheses is positive, because $n\sin {\rho }_0\cos {\rho }_0=\sqrt{n-1}$ and $(n-1)c_n<\sqrt{n-1}$. It increases up to $\pi /4$ and then decreases strictly to a negative value at $\pi /2$. Hence it crosses zero exactly once on $[{\rho }_0,\pi /2]$, from positive to negative. The minimum of $F$ is again an endpoint value; $F({\rho }_0)\ge 0$ and $F(\pi /2)=1/2$. This proves the stronger range of the spherical cap area upper bound:

Let $m$ be the number of facets of the convex polytope $P$. Its facet description can be writtenBecause $r^{-1}{B}^n\subset P$, each supporting closed half-space has $h_j\ge 1/r$. For any $\theta \in S^{n-1}$, follow the ray $t\theta$ to its last point in $P$. Its radius $t_{\theta }$ is at most one because $P\subset B^n$. At least one facet is active there, givingThus the unit sphere is covered by the $m$ spherical caps centred at $u_j$ with angular radius $\rho =\arccos (1/r)$. Since $r\ge \sqrt{2}$, this radius lies in $[\pi /4,\pi /2)$ and the spherical cap area upper bound applies. Subadditivity of surface area givesUsing $\log (1-x)\le -x$ for $0<x<1$,The facet lower bound for ball approximations is exponential in the dimension.

Choose a maximal subset $U\subset S^{n-1}$ whose distinct points have Euclidean distance greater than one. The volumetric bound for Euclidean metric nets makes the construction finite: the open Euclidean balls of radius $1/2$ about the points of $U$ are disjoint and all lie in $(3/2)B^n$, soMaximality means that $U$ is a metric net of radius one on the unit sphere. Thus every $\theta \in S^{n-1}$ has some $u\in U$ with $\Vert u-\theta \Vert \le 1$. Since both are unit vectors,Now intersect the corresponding closed half-spaces:The Cauchy-Schwarz inequality shows that $(1/2)B^n\subset P$. Conversely, write any nonzero $x\in P$ as $x=t\theta$ and choose $u$ as above. Then $t/2\le t(u\cdot \theta )=u\cdot x\le 1/2$, so $t\le 1$. Hence $P\subset B^n$, which also proves boundedness. This convex polytope has at most $|U|\le 3^n$ facets, since redundant inequalities can only reduce their number. It meets the required inclusions with $r=2$.

The useful form is Talagrand's convex distance inequality. Let $({\Omega }_i,{\mu }_i)$ be standard probability spaces, let $\Omega ={\prod }_{i=1}^n{\Omega }_i$ carry the product measure $\mu ={⨂}_i{\mu }_i$, and let $A\subset \Omega$ be a measurable event with $\mu (A)>0$. For $x\in \Omega$, form the mismatch vectorsThe Talagrand convex distance is the distance from zero to their closed convex hull:Equivalently, by the Hahn-Banach separation theorem for two convex sets,Nonnegative weights suffice because every mismatch vector has nonnegative coordinates. Talagrand's convex distance inequality statesIn particular, Markov's inequality gives the product-space concentration inequalityThe same conclusion is interpreted with outer probabilities if a distance set is not measurable; the continuous geometric function used below has measurable level sets. A median $M$ of a real random variable $Z$ means that $\mathbb{P}(Z\le M)\ge 1/2$ and $\mathbb{P}(Z\ge M)\ge 1/2$. Applying the displayed concentration inequality to suitable level sets will control deviations around a median.

Interpret $Y_n$ as the length of a shortest Euclidean travelling salesman tour, and take the points to be independent random variables with the uniform distribution on the square. We assume $n\ge 2$; a closed tour on one point has length zero, so the printed lower bound would be false for $n=1$. For two points the closed tour traverses the joining segment twice.

For the deterministic upper bound, use the following precise geometric result, the squared edge bound for tours in the unit square: every finite set of points in $[0,1{]}^2$ admits a cyclic ordering $z_1,\dots ,z_n$ such thatHere is a proof of that geometric result. First consider a right triangle with hypotenuse endpoints $a,b$, hypotenuse length $c$, and right-angle vertex $v$. The quadratic path bound in a right triangle supplies a path from $a$ to $b$ through any finite set inside the triangle whose sum of squared edge lengths is at most $c^2$. For an empty set use the edge $ab$. For a single point $z$, use $a,z,b$: the triangle lies in the disk with diameter $ab$, so $\angle azb\ge \pi /2$ and the law of cosines gives $\Vert a-z{\Vert }^2+\Vert z-b{\Vert }^2\le c^2$.

For several points, draw the altitude from $v$ to the hypotenuse. It splits the triangle into two smaller right triangles with hypotenuses $av$ and $vb$. Their squared hypotenuse lengths sum to $c^2$ by the Pythagorean theorem. Repeated altitude subdivision eventually makes every cell small enough to contain at most one of the given distinct points: each child is similar to the original triangle and its diameter contracts by at most the fixed factor $\max (\Vert a-v\Vert ,\Vert b-v\Vert )/c<1$. Construct the base-case paths and combine them from the bottom of this finite subdivision tree. The two child paths concatenate at $v$. If $v$ is an auxiliary point, delete it by joining its two neighbours directly. Both neighbours lie in the right-angle sector of the parent triangle at $v$, so their angle at $v$ is at most $\pi /2$. The law of cosines now shows that this shortcut does not increase the sum of squared edge lengths. The combined path still has endpoints $a,b$ and squared cost at most $c^2$.

One can first put the given points in generic positions, avoiding subdivision boundaries, and then pass to a limit. There are only finitely many possible visiting orders, so a subsequence keeps the same order and its squared cost converges; this also handles coincident locations. No assumption about a minimum separation remains in the result.

Split the square along a diagonal $ab$. Apply the triangle result in each half, following one path from $a$ to $b$ and the other back to $a$. Each half contributes at most $\Vert a-b{\Vert }^2=2$. Remove either diagonal endpoint if it was auxiliary. At a square corner all neighbours lie in a sector of angle $\pi /2$, so the same squared-cost shortcut applies. This gives the asserted cyclic ordering with total squared cost at most four. It does not assert that the tour minimizing ordinary length itself has this squared-edge property. The Cauchy-Schwarz inequality applied to the tour supplied by the theorem provesThus the upper bound is deterministic, independently of the sampling law.

For the lower bound, put $R_i={\min }_{j\ne i}\Vert X_i-X_j\Vert$, the nearest neighbour distance at $X_i$. Both edges incident to $X_i$ in any closed tour have length at least $R_i$. Summing over vertices and then dividing by two gives $Y_n\ge {\sum }_i{R}_i$. Conditional on $X_i=x$, the union bound and the uniform distribution giveBoundary clipping only makes the ball smaller. Apply the layer cake representation of the expected value, restricting the integral to $0\le t\le 1/(2\sqrt{n})$:Linearity of the expected value now yieldsThe unspecified sampling phrase in the paper must therefore be understood as independent uniform sampling: an arbitrary distribution concentrated in a tiny region cannot satisfy this lower bound.

Write $f(x)=\mathrm{TS}\{x_1,\dots ,x_n\}$. Besides Talagrand's convex distance inequality, we use the precise squared edge bound for tours in the unit square stated above and the triangle inequality, which permits shortcutting a closed walk without increasing its length. We first prove the geometric comparison that connects these results.

For each fixed $x$, choose a cyclic tour $C$ with edge lengths ${\ell }_i$ satisfying ${\sum }_i{\ell }_i^2\le 4$. At vertex $x_i$, let $a_i(x)$ be the sum of the lengths of its two incident edges in $C$. The Cauchy-Schwarz inequality givesWe claim the weighted mismatch bound for Euclidean tours:To prove it, keep the vertices whose coordinates agree. In the cyclic ordering $C$, the deleted vertices split into consecutive runs between kept vertices. For one run, let $a,b$ denote its two boundary edge lengths and $S$ the sum of its internal edge lengths. Starting at the left kept endpoint, visit the run and return along the same path, at cost $2(a+S)$; starting at the right endpoint costs $2(b+S)$. Choose the cheaper detour. Its cost is at mostwhich is exactly the sum of $a_i(x)$ over that run. Attach these detours to a shortest tour through $y$, which already visits every kept point. The resulting closed walk visits all points of $x$; shortcut it using the triangle inequality. Summing the detour costs proves the claimed weighted mismatch bound for Euclidean tours. If there is just one kept vertex, the same argument uses that vertex as both endpoints of the unique run. If there are no kept vertices, $f(x)\le {\sum }_i{\ell }_i\le {\sum }_i{a}_i(x)$ proves the comparison directly. Repeated point locations cause no difficulty, since their connecting edges may have length zero.

Let $M$ be any median of $f(X)$ and set $A=\{y:f(y)\le M\}$. For $f(x)\ge M+t$, the weighted mismatch bound for Euclidean tours impliesThe weights have squared sum at most one, so $d_T(x,A)\ge t/4$. Since $\mathbb{P}(A)\ge 1/2$, Talagrand's convex distance inequality yieldsFor the lower tail, put $B=\{x:f(x)\le M-t\}$. If $\mathbb{P}(B)=0$ there is nothing to prove. For every $y$ with $f(y)\ge M$, apply the same weighted mismatch bound for Euclidean tours with its weights $a_i(y)$ and all $x\in B$. It gives $d_T(y,B)\ge t/4$. The set of such $y$ has probability at least $1/2$, so Talagrand's convex distance inequality instead givesCombining both tails,The bound has a constant fluctuation scale, independent of $n$. Only independence of the point coordinates and their support in the square are needed here; their uniform distribution was needed for the earlier lower bound on the expected value.

Let $X_s$ count the copies of the complete graph $K_s$ in the binomial random graph $G_{n,p}$. By linearity of the expected value and independence of distinct edges,Throughout, $n$ is sufficiently large that $k=\lfloor \log \log n\rfloor \ge 2$. We have $k\to \infty$, $k=O(\log \log n)$ and $k\log k=o(\log n)$.

First, since $p=n^{-2/k}$,The first moment method proves $\mathbb{P}(X_{k+1}>0)=o(1)$.

For the existence of a $k$-clique, put $X=X_k$ and $\mu =\mathbb{E}X$. Since $p^{\left(\genfrac{}{}{0ex}{}{k}{2}\right)}=n^{-(k-1)}$,This alone is insufficient: we must control the variance via the overlap formula for the variance of a clique count. Let $I_S$ indicate that a given $k$-set $S$ spans a clique. If $|S\cap T|=j$, the two copies share $\left(\genfrac{}{}{0ex}{}{j}{2}\right)$ edges, soFor $j=0,1$ their edge sets are disjoint and the covariance vanishes, even when they share one vertex. Counting ordered pairs of $k$-sets gives the exact formulaThis includes the diagonal case $j=k$.

To bound the overlap factor, regard it as the probability that a uniformly chosen $k$-set $T$ intersects a fixed $S$ in exactly $j$ vertices. A union bound over the possible specified $j$-subsets of $S$ yieldsHere $(a{)}_j=a(a-1)\cdots (a-j+1)$ is a falling factorial, and the last bound holds for $n\ge 2k$. ThereforeFor $2\le j\le k$, the concave quadratic $j(k-j+1)$ is minimized at an endpoint. Its endpoint values are $2(k-1)$ and $k$, both at least $k$. Thus every power of $n$ in the last sum is at most $n^{-1}$, andbecause the logarithm of its numerator is $O(k\log k)=o(\log n)$. The second moment method, or Chebyshev's inequality directly, gives $\mathbb{P}(X=0)=o(1)$. Finally, every larger clique contains a $(k+1)$-clique, so the absence of $K_{k+1}$ excludes all larger sizes. The clique number is exactly $k$ with high probability: