Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 11 (Graphs and Hypergraphs)

Write $K_j(t)$ for a balanced complete multipartite blow-up, with $j$ parts each containing $t$ vertices. Its occurrence is a subgraph condition, so additional internal edges in the host are harmless. The coefficient multiplying $\log n$ is essential: the PDF has $t=\lfloor d\log n\rfloor$, although it is lost in the converted TeX.

First prove the common neighbourhood from bipartite density estimate. Suppose a bipartite graph has parts of sizes $m,N$ and at least $\beta mN$ edges. For an integer $s\le \beta m/2$, count incidences between $s$-subsets of the first part and their common neighbours in the second. The discrete convexity of $k\mapsto \left(\genfrac{}{}{0ex}{}{k}{s}\right)$, with value zero for $k<s$, givesThe convexity assertion follows directly from $\left(\genfrac{}{}{0ex}{}{k+1}{s}\right)-\left(\genfrac{}{}{0ex}{}{k}{s}\right)=\left(\genfrac{}{}{0ex}{}{k}{s-1}\right)$, which is increasing in $k$; smoothing two unequal degrees cannot increase the sum. In the binomial ratio every factor is at least $\beta /2$, because $\lfloor \beta m\rfloor -s+1\ge \beta m-s\ge \beta m/2$. Consequently some $S$ satisfies

We prove the logarithmic clique blow-up from minimum degree by induction on $r$. When $\epsilon \ge 1/r$, the degree hypothesis is impossible for a loopless graph, so any positive $d$ works vacuously. Assume $0<\epsilon <1/r$. For $r=1$, take two copies of the vertex set and join the copies of adjacent vertices. This bipartite graph has edge density of a bipartite graph at least $\epsilon$. ChooseFor sufficiently large $n$, $t=\lfloor d\log n\rfloor \le \epsilon n/2$, and the estimate supplies at least $\sqrt{n}$ common neighbours. Choose $t$ of them. The two selected sets are disjoint in the original graph, since a selected vertex cannot be adjacent to itself. They give $K_2(t)$.

For $r\ge 2$, put ${\epsilon }^{\prime }=\epsilon +1/(r-1)-1/r$. The same minimum degree of a graph exceeds $(1-1/(r-1)+{\epsilon }^{\prime })n$. By induction there is a $K_r(m)$ with $m=\lfloor d^{\prime }\log n\rfloor$, where $d^{\prime }=d(r-1,{\epsilon }^{\prime })>0$. Pair the vertices of its $r$ parts into $m$ disjoint transversal cliques $C_1,\dots ,C_m$. Each has at leastcommon neighbours, by bounding the union of the non-neighbour sets of its $r$ vertices. Set $\beta =\min \{r\epsilon ,1/2\}$. Form the bipartite graph whose first part is these $m$ cliques, with $C_i$ joined to a vertex when that vertex is a common neighbour of all of $C_i$. It has density at least $\beta$. ChooseFor large $n$, $m\ge d^{\prime }\log n/2$ and $t=\lfloor d\log n\rfloor \le \beta m/2$. The estimate gives $t$ selected cliques and at least $\sqrt{n}\ge t$ common vertices. The selected cliques supply $t$ vertices in each of the original $r$ parts, and their common vertices supply the final part. No common vertex belongs to a selected clique, again because there are no loops. All required cross-part edges are present. Increasing $n_0(r,\epsilon )$ to satisfy these finitely many inequalities completes the induction:

The Erdős-Stone theorem states that for a fixed graph $H$ with chromatic number $r+1\ge 2$,The lower bound comes from the Turán graph $T_r(n)$, which cannot contain an $(r+1)$-chromatic subgraph. To obtain the upper bound from our minimum-degree result, suppose $e(G)\ge (a+\eta )n^2/2$, where $a=1-1/r$ and $0<\eta <1-a$. Repeatedly delete a vertex of degree less than $b$ times the current order, where $b=a+\eta /2$, until no such vertex remains. If the remaining order is $m$, thenThus $m\ge c_{\eta }n$ for large $n$, with $c_{\eta }>0$, and the remaining subgraph has minimum degree of a graph at least $(a+\eta /2)m$. It contains $K_{r+1}(\lfloor d\log m\rfloor )$. A proper graph colouring of $H$ places its vertices in the $r+1$ parts once their size exceeds $|V(H)|$. This contradicts $H$-freeness. Adjusting a fixed positive density margin absorbs the difference between $n^2/2$ and $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, proving the upper bound.

The six-vertex forbidden graph is the octahedral graph $K_{2,2,2}$: the deleted matching in a graph gives its three independent pairs. Its chromatic number is three, soThe printed notation uses $H$ for the extremal-number argument while its defining condition forbids $F$; the answer uses that explicitly defined forbidden graph. For the strict finite inequality, take $T_2(n)$ and add one edge inside its larger part, which has at least two vertices for $n\ge 3$. Every triangle in a graph then uses this added edge. However, $K_{2,2,2}$ contains two vertex-disjoint triangles in a graph, obtained by taking one vertex from each pair and then the other three. It therefore cannot occur in the constructed graph. Hence

Use the equitable form of the Szemerédi regularity lemma. For $0<\epsilon <1/2$ and a prescribed lower bound $m_0$, there are $M,n_0$ such that every sufficiently large graph admits a set partitionwith at most $\epsilon k^2$ unordered irregular pairs among the nonexceptional cells. A uniform pair here means a regular pair of vertex sets. Larger values of $\epsilon$ follow from a smaller parameter, so the stated restriction loses nothing.

For the proof, retain the exceptional vertices as singleton cells in an auxiliary set partition $\mathcal{P}$. Define its regularity energy by the ordered sumFor diagonal rectangles the adjacency matrix of a graph defines $d(A,A)$; diagonal terms are included. Thus $0\le q\le 1$. If $A\times B$ is split into rectangles of densities $d_{uv}$ and sizes $w_{uv}$, their weighted mean is $d=d(A,B)$. Expanding squares proves the refinement variance identity for regularity energy:Every refinement therefore increases or preserves energy.

Suppose equal cells $V_i,V_j$ of size $m$ are $\epsilon$-irregular. Choose witnesses $X\subseteq V_i$, $Y\subseteq V_j$ of sizes at least $\epsilon m$, whose density differs from $d(V_i,V_j)$ by more than $\epsilon$. Refine the cells so that these witnesses are unions of refined atoms. Applying the Cauchy-Schwarz inequality inside $X\times Y$ gives an increase, for this oriented rectangle, greater thanChoose witnesses simultaneously for every irregular pair. Each original cell is cut by at most $k-1$ witness sets and has at most $2^k$ atoms. If more than $\epsilon k^2$ unordered pairs are irregular, both orientations contribute, givingas long as the exceptional set has at most $n/2$ vertices.

To restore equal sizes without sacrificing this increase, use equalization with a controlled exceptional set. Cut every witness atom into blocks of size $\ell =\lfloor m/4^k\rfloor$, leaving fewer than $\ell$ unused vertices in each atom. Make each unused vertex a singleton exceptional cell. This is a further refinement, so there is no energy loss. The number newly exceptional is at mostWhen $m\ge 2\cdot 4^k$, the new nonexceptional cell count $k^{\prime }$ is at most $4k{4}^k$: indeed $\ell \ge m/(2\cdot 4^k)$ and $n/m\le 2k$. It is at least $k$, since each old cell supplies at least $4^k-2^k\ge 1$ blocks.

Let $L=\lceil 2{\epsilon }^{-5}\rceil +1$. Choose the initial count $k_0\ge m_0$ so large that $L{2}^{-k_0}\le \epsilon /2$, and begin with $k_0$ equal cells and fewer than $k_0$ leftover vertices. Take $n_0$ large enough that these initial leftovers are at most $\epsilon n/2$. Iterate the bound $k\mapsto 4k{4}^k$ for $L$ rounds to obtain a finite number $M$. Increase $n_0$ further to ensure $n\ge 4M{4}^M$. Then every cell size encountered satisfies $m\ge n/(2M)\ge 2\cdot 4^k$, so every equalization is legitimate. The total exception budget is at most $\epsilon n$, because the initial losses use half the budget and all later losses sum to at most $Ln{2}^{-k_0}$. Energy cannot increase by more than one, so $L$ failing rounds are impossible. The process must stop with at most $\epsilon k^2$ irregular pairs. This proves the Szemerédi regularity lemma, including the bounded cell count, equitability and exceptional-set control.

For the dense-pair application, apply this proof with $\eta =1/100$ and $m_0=100$. Suppose every $\eta$-regular pair of nonexceptional cells has density at most $1/4$. Edges touching $V_0$ number at most $\eta n^2$. Edges inside nonexceptional cells number at most $k{m}^2/2\le n^2/(2m_0)$. The at most $\eta k^2$ irregular cell pairs contribute at most $\eta n^2$. Finally the regular cross-cell pairs contribute at most $k(k-1)m^2/8\le n^2/8$. Thereforea contradiction. Some regular pair $(U,W)$ consequently has density greater than $1/4$. It is also a $1/8$-uniform pair, since subsets of relative size at least $1/8$ qualify in the stronger $\eta$-regularity condition. The common cell size satisfies $m\ge (1-\eta )n/M\ge n/(2M)$. Thus the dense regular pair from edge surplus givesThis first proves the assertion for $n\ge n_0$. For the finitely many smaller possible orders, choose the endpoints of any edge as singleton sets: the pair has density one and is regular for every positive parameter. Taking $c=\min \{1/(2M),1/n_0\}>0$ includes these cases as well.

Both alternatives can be proved. For the oriented tree alternative take $n\ge 2$; at $n=1$ the displayed tournament order is zero, so that unqualified boundary case cannot be intended.

Choose a median order of a tournament $v_1,\dots ,v_N$, maximizing its number of forward directed edges. Every interval inherits a median order, since improving that interval would improve the whole order. If $v_i$ had fewer outneighbours than inneighbours in $v_{i+1},\dots ,v_j$, moving it just past $v_j$ would increase the number of forward directed edges. Hence it has at least half the vertices of that later interval as outneighbours.

Call a graph embedding half-sparse if every proper final interval $I$ satisfies $|f(T)\cap I|<|I|/2+1$. This half-sparse median-order embedding admits a useful extension. Suppose an outward leaf is attached to a vertex mapped to $v_i$, and reserve two extra vertices at the end of the tournament order. In the old interval after $v_i$, half-sparsity bounds the number of occupied vertices by less than half its size plus one. The interval extended by two vertices has at least that half-size plus one outneighbours of $v_i$. Thus at least one outneighbour is free; map the new leaf there. Every old final interval has gained two available places and at most one new image, so its strict inequality persists. Final intervals wholly within the two new places contain at most one image, so they also satisfy the inequality. This proves the extension, not just an existence assertion about degrees.

Starting with an directed edge in a two-vertex tournament and repeatedly attaching outward leaves proves that every $h$-vertex arborescence embeds half-sparsely in every $(2h-2)$-vertex tournament for $h\ge 2$. The root-first construction supplies the induction. An unused suffix can be appended without destroying the inequality; for a suffix which contains the whole old order the extra place supplies the needed strictness. A singleton embeds half-sparsely in the first vertex of a two-vertex order. Reversing the oriented tree and tournament gives ordinary embeddings of reversed arborescences in $2h-2$ vertices as well.

Here is the stronger invariant needed for an arbitrary oriented tree. Root it at a source. Classify each directed edge as forward or backward according to whether it points away from or towards the root in the underlying rooted tree. Let $b$ be the number of backward directed edges and $c$ the number of nonempty connected components made of these directed edges, ignoring isolated vertices. Put $d=b-c$. We claim that the oriented tree has a half-sparse embedding in every median-ordered tournament of order $2n+2d$.

Induct on the oriented tree order. If it has a forward leaf, delete that leaf, use the induction hypothesis and apply the two-place extension. Neither $b$ nor $c$ changes. If there are no backward directed edges, use the arborescence construction. Otherwise first remove forward leaves as above, so every remaining leaf is backward. Choose a backward component furthest from the root. It must be a pendant subtree: a forward continuation below it would either reach another backward component, contrary to its choice, or end at a forward leaf. Let this component have $h\ge 2$ vertices and top vertex $y$. Since the root is a source, $y$ is not the root; its joining directed edge from its parent $x$ is forward. The component is an reversed arborescence rooted at $y$.

Delete the component. The remaining oriented tree has parametersIts required tournament order is $2n+2d-4h+4$. Embed it in the initial interval of this length. Temporarily attach $2h-2$ outward leaves at $x$, using the extension lemma repeatedly. This consumes exactly $4h-4$ extra places and gives a half-sparse embedding of the enlarged oriented tree in the original tournament. The $2h-2$ temporary images all lie in the outneighbourhood of $f(x)$; among them embed the deleted reversed arborescence. Its root automatically receives the joining directed edge from $f(x)$. Replace the temporary leaves by this component. The final image is a subset of the temporary enlarged image, so half-sparsity survives. This proves the invariant with the precise count, including the case when the remaining oriented tree is a singleton.

Unless the oriented tree is already an in- or out-arborescence, every rooting has at least one backward component. Choose one orientation, reversing all directed edges if necessary, so that some rooting has at most $(n-1)/2$ backward directed edges. It then has $d\le (n-3)/2$. Within this fixed orientation choose the root to minimize $(d,b)$ lexicographically. If a neighbour pointed into the root, move the root across that directed edge. Only this directed edge changes its forward/backward classification. Removing it from the backward forest decreases $b$ by one and decreases $c$ by at most one; hence it cannot increase $d$, and when $d$ stays equal it strictly decreases $b$. This contradicts the chosen minimum. Thus the chosen root is a source, while its $d$ retains the required bound. Reversal does not affect a universal tournament-embedding assertion, because one reverses the host tournament too. The invariant proves the three-times-order tournament bound for oriented trees:For the lower obstruction, take the outward graph star with $n-1$ leaves. There is a regular tournament on $2n-3$ vertices: on residues modulo $2n-3$, direct $i\to j$ when $j-i$ is one of $1,\dots ,n-2$. Every vertex has outdegree $n-2$, so none can be the centre of that outward star. Thus the universal bound cannot be reduced to $2n-3$.

For the strongly connected directed graph alternative, the correct universal assertion is an upper bound by the independence number, together with examples needing that many directed circuits. The literal assertion that every such graph needs $\alpha (D)$ directed circuits is false: a directed four-cycle has independence number two and is spanned by one directed circuit. Work with a nontrivial strongly connected digraph; a loopless singleton has no directed circuit.

Use the permitted coherent cyclic order of a digraph. Representatives differ by cyclic rotations and swaps of consecutive nonadjacent vertices. In every representative, a backward directed edge $v_j\to v_i$ has a forward directed path from $v_i$ to $v_j$. A directed circuit with one backward directed edge winds once around the order. Every vertex belongs to such a directed circuit, because every vertex has an outgoing directed edge and coherence puts that directed edge on a once-winding directed circuit. Let $k$ be the cyclic stability of a digraph order: the largest size of an independent set consecutive in an equivalent order. Then $k\le \alpha (D)$.

We need a short ordering lemma. If a set $X$ has no forward path between distinct members, then $|X|\le k$. Among equivalent representatives retaining this property, minimize the span from its first to its last member. Suppose there is a vertex in a gap. If some gap vertex $y$ cannot be reached from an earlier member of $X$ by a forward path, take the first such $y$. Every preceding gap vertex in the span is reachable from an earlier member of $X$. It follows that $y$ has no forward incoming directed edge from anywhere in that part of the span; a backward outgoing directed edge to it is also impossible, since coherence would supply the same forbidden forward reachability. Thus $y$ is nonadjacent to every intervening vertex and can be moved before the first member of $X$, shortening the span. Otherwise every gap vertex is reachable from an earlier member of $X$. Take the last one. It cannot have a forward path to a later member of $X$, and coherence consequently rules out directed edges in either direction to the following members of $X$. Move it past them, again shortening the span. Swaps of nonadjacent vertices do not change the forward-edge graph, so these moves preserve the hypothesis. Both cases contradict minimality. Therefore $X$ is consecutive. It is independent: a forward directed edge is forbidden by hypothesis, and a backward directed edge would imply a forward path by coherence. Rotate it to the start to obtain $|X|\le k$.

Choose a representative starting with a stable block $S=\{s_1,\dots ,s_k\}$. Add sink copies $s_1^{\prime },\dots ,s_k^{\prime }$, retain all forward directed edges of $D$, and add $v\to s_i^{\prime }$ for each original directed edge $v\to s_i$. This is an acyclic auxiliary directed graph $A$. A once-winding directed circuit through $s_i$ cannot visit another block member, since no forward path can join two members of this initial independent block. Opening this directed circuit gives a path from $s_i$ to $s_i^{\prime }$ in $A$.

The partial order defined by reachability in $A$ has width exactly $k$. The sink copies already form an antichain of size $k$. For the reverse inequality, let $X$ be an antichain and let $J$ index its sink copies. Permute the independent initial block so that these labels come first, then rotate that part of the block to the end. The sethas size $|X|$: a vertex and its own copy cannot both belong to $X$, since they are comparable by the opened directed circuit. There is no forward path between distinct members of $Y$ in the rotated order. A path between original members would give comparability in $A$; a path from an original member to $s_j$ would become a path to its sink copy, also forbidden. No forward path leaves the final stable block. The ordering lemma therefore gives $|X|=|Y|\le k$.

Apply the Dilworth theorem to partition this reachability order into $k$ chains in a partial order. Each chain contains exactly one original block vertex and exactly one sink copy, since each of these two antichains has size $k$; these are its first and last elements. Expand consecutive chain relations into directed paths in $A$. The paths cover all vertices, though intervening vertices can occur on several paths. Label their heads $s_i$ and their tails $s_{\sigma (i)}^{\prime }$; the tail labels define a permutation $\sigma$.

Among all such covering path families maximize the number of cycles of $\sigma$. If two paths whose labels lie in the same permutation cycle meet at a vertex, exchange their suffixes there. The paths remain simple, since the auxiliary graph is acyclic, and their union still covers the same vertices. Exchanging the two tail labels splits that permutation cycle into two, a contradiction. Thus paths in the same permutation cycle are disjoint. Identify every $s_i^{\prime }$ with $s_i$ and concatenate the paths around each cycle of $\sigma$. Each concatenation is a genuine directed circuit, with no repeated vertex except its closing vertex. Together these directed circuits cover $D$, and there are at most $k\le \alpha (D)$ of them. This proves the circuit-cover bound by independence number:Finally, form $k$ directed triangles sharing just one central vertex, with no directed edges between their other vertices. This strongly connected directed graph has independence number $k$, by taking one outer vertex from each triangle. A simple directed circuit can use only one triangle, since visiting a second requires repeating the centre. Exactly $k$ directed circuits are therefore necessary. The bound $\alpha (D)$ is sharp in general; $\alpha (D)-1$ is not a universal bound.

The unrestricted identity needs qualification. A Fano plane has seven vertices of a hypergraph, so the complete three-uniform hypergraph on six vertices of a hypergraph avoids it and has twenty edges, whereas the displayed balanced-part count is eighteen. On five vertices of a hypergraph the corresponding numbers are ten and nine. Thus the intended extremal theorem is the sufficiently-large-$n$ Fano-plane Turán theorem. We describe its stability proof, including the exact counting step that upgrades an asymptotic result to equality.

Identify the Fano points with the nonzero vectors of ${\mathbb{F}}_2^3$, and its hyperedges with triples summing to zero. It has no Property B. Indeed, a line-free set has at most four points: if a set $A$ of nonzero vectors contains no zero-sum triple and $a\in A$, the sets $A\setminus \{a\}$ and $a+(A\setminus \{a\})$ are disjoint subsets of the six nonzero vectors other than $a$, so $|A|\le 4$. Moreover, if $|A|=4$, those two three-element sets partition those six vectors. Write $A=\{a,b,c,d\}$. The sum $b+c$ lies outside $A$, so belongs to $a+(A\setminus \{a\})$. It is neither $a+b$ nor $a+c$, and must therefore equal $a+d$. Thus $a+b+c+d=0$. The other three points have sum zero because the sum of all seven nonzero vectors is zero. They therefore form a line. In any two-colouring one colour has at least four points: if it contains a line we are done, and otherwise the other colour contains a line. This proves non-two-colourability.

Partition the host vertices of a hypergraph into sizes $a,b$ and take all triples meeting both parts. This bipartite three-uniform hypergraph has Property B and is consequently Fano-free. Its edge count isThe product $ab$ is maximized at balanced integer sizes. Writingwe have the exact lower bound $\mathrm{ex}(n,F)\ge b(n)$, and $b(n)=(3/4+o(1))\left(\genfrac{}{}{0ex}{}{n}{3}\right)$.

The structural step is Fano stability: a Fano-free hypergraph with density sufficiently close to $3/4$ has a bipartition with at most $\rho n^3$ internal triples, for any prescribed $\rho >0$. Its proof studies four hypergraph link graphs around a complete four-vertex three-uniform configuration. Colour a pair by the link vertices of a hypergraph containing it. Three perfect matchings in a graph on four other vertices of a hypergraph, with distinct colours corresponding to a triple of the configuration, would complete a Fano copy. Thus these rainbow patterns are forbidden. The near-extremal total link degree forces, after removing a small exceptional set, an almost balanced pattern with pair multiplicity two within the two classes and four between them. Internal triple density bounded away from zero produces many complete tripartite six-vertex templates; the nearly complete links then supply three paired neighbours and complete a Fano plane. Consequently the internal triple density tends to zero. These are the main ingredients of the stability argument: link degree counting supplies the approximate partition, and the forbidden completion templates eliminate positive internal density.

To see concretely why stability gives the exact bound, suppose $e(H)\ge b(n)$, and first obtain high minimum hypergraph vertex degree. Delete any vertex of degree at most $3m^2/8-2m$ when the current order is $m$. Directly from the formula for $b$, for large $m$,After deletions down to order $m$, the remaining hypergraph therefore has at least $b(m)+n-m$ edges. It cannot reach $m=\lceil n^{1/3}\rceil$, since this exceeds $\left(\genfrac{}{}{0ex}{}{m}{3}\right)$ for large $n$. The process stops at an order still tending to infinity, with minimum degree of a graph greater than $3m^2/8-2m$. If the high-minimum-degree case has at most $b(m)$ edges, any deletion gives a contradiction. Thus it suffices to treat that case; rename its order $n$.

Apply stability with a very small constant, for example $\rho =10^{-12}$, and choose a partition $A\bigsqcup B$ minimizing the number of internal hyperedges. Its part sizes are close to $n/2$, since its cross-part capacity is $|A||B|(n-2)/2$, and $e(H)\ge b(n)$ leaves at most $\rho n^3$ available compensation for any imbalance. In particular $||A|-n/2|,||B|-n/2|\le 2\sqrt{\rho }n$ for large $n$. Optimality also giveswith the analogous inequality for $x\in B$: otherwise moving $x$ would reduce the internal count.

Suppose some $x\in A$ has more than $n^2/100$ edges in its same-side link. Its opposite-side link then has at least as many. Each link has a matching in a graph of size at least $\lfloor n/300\rfloor$: the endpoints of a maximal matching in a graph cover every edge, so a matching in a graph of size $s$ bounds the link edge count by $2sn$. For each choice of one matching in a graph edge in $A$ and two matching in a graph edges in $B$, the six vertices of a hypergraph plus $x$ would form a Fano plane if all transversal triples through the three pairs were present. Specifically take the three triples through $x$ and the four even-parity transversal triples. Hence at least one of these cross-part triples is missing. The matchings in a graph are disjoint, so different choices give different missing triples. There are at leastFor large $n$ this exceeds $\rho n^3$, contradicting the edge count: the missing cross triples already outweigh every internal triple. Thus every same-side link has at most $n^2/100$ edges.

If an internal triple $xyz\subseteq A$ remains, high minimum degree of a graph gives, for each of its vertices of a hypergraph,The intersection of the three opposite-side links therefore has at least their total edge count minus $2\left(\genfrac{}{}{0ex}{}{|B|}{2}\right)$. Using $|B|\le (1/2+2\sqrt{\rho })n$, this exceeds $|B{|}^2/3$ for large $n$. By the quadratic Turan theorem bound, their intersection contains $K_4$. Its three perfect matchings in a graph, assigned to $x,y,z$, together with $xyz$ are the seven edges of a Fano plane. This is precisely Fano completion through three matchings, and gives a contradiction. The same argument excludes internal triples in $B$.

Thus the high-minimum-degree hypergraph is genuinely bipartite, not merely approximately so, and has at most $b(n)$ edges. The deletion argument proves the same bound for the original hypergraph. Combining with the balanced construction yieldsThis proof description keeps the essential roles distinct: non-two-colourability gives the lower construction, link-graph stability gives an approximate partition, and the minimum-degree/matching in a graph argument removes the last internal edges. The ceiling in the final term is confirmed by the PDF; the converted TeX incorrectly repeats the floor.