Write $W_n(i,j)$ for the number of locally admissible words $(x_0,\dots ,x_n)$ with $x_0=i$ and $x_n=j$. Here local admissibility means $A_{x_r{x}_{r+1}}=1$ for each consecutive pair; length counts symbols, so there are $n$ transitions. For $n=0$, the single-symbol word gives $W_0(i,j)={\delta }_{ij}=(A^0{)}_{ij}$, and for $n=1$ we have $W_1(i,j)=A_{ij}$.

To append the last symbol $j$, choose the penultimate symbol $k$. Every choice gives a locally admissible word exactly when its length-$n$ prefix is locally admissible and $A_{kj}=1$. Different prefixes or penultimate symbols give different words, and every admissible word is obtained once. ThereforeThis is precisely the rule for matrix multiplication. Mathematical induction consequently givesEquivalently, expanding the matrix entry sums the products $A_{i{x}_1}{A}_{x_1{x}_2}\cdots A_{x_{n-1}j}$ over all intermediate symbols; each product is the indicator function of one allowed transition chain.

The intended meaning of “allowed” here is local admissibility. If instead it means a word that actually occurs in some two-sided sequence in ${\Sigma }_A$, the assertion needs an additional extension assumption. For example, $A=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$ permits the word $(1,2)$ and has $(A{)}_{12}=1$, but ${\Sigma }_A$ is empty because no symbol can continue after $2$. Having a nonzero entry in every row and every column is sufficient: one can successively choose a predecessor and a successor to extend every locally admissible word indefinitely in both directions. No such assumption is needed for the local counting formula.

A fixed point of the left shift satisfies $x_{k+1}=x_k$ for every $k\in \mathbb{Z}$, so its entire two-sided sequence is constant. The constant sequence with value $i$ belongs to the subshift of finite type precisely when $A_{ii}=1$: this is exactly the requirement that its repeated transition be allowed by the symbolic transition matrix. There is one such fixed point for each diagonal entry equal to one. ThusThis also covers an empty subshift of finite type, for then no permitted constant sequence exists.

Since $X$ is an irreducible variety, every nonempty open subset is irreducible and the sheaf of nonzero rational functions on an irreducible variety has value $k(X{)}^{\ast }$ there. All its restriction maps between nonempty opens are identities, and restriction to the empty set is surjective. Thus ${\mathcal{K}}_X^{\ast }$ is a flabby sheaf, and the introductory argument gives $H^1(X,{\mathcal{K}}_X^{\ast })=0$.

Apply the long exact sequence in sheaf cohomology to the short exact sequence of sheavesIts relevant portion isThe connecting homomorphism is therefore surjective, with kernel the image of $k(X{)}^{\ast }$. The computation in part (a) now givesConcretely, local rational equations $f_i$ of a divisor on an algebraic curve differ by regular units on overlaps. Their ratios give the gluing data of an invertible sheaf; changing the local equations by units changes those data by a coboundary. This is the transition-function interpretation of the identification with the Picard group. Reversing all transition ratios replaces a class by its inverse; either consistent convention gives the same group isomorphism.

For a divisor on an algebraic curve $D=\sum n_{P}P$, define its line bundle associated to a divisor inside the sheaf of rational functions byLocally choose a rational equation $f_i$ for $D$, as in the construction of the quotient sheaf above. ThenConsequently this is an invertible sheaf. Multiplication gives an isomorphismas is checked on the displayed local generators. If $D=\mathrm{div}(f)$, multiplication by $f$ identifies ${\mathcal{O}}_X(D)$ with ${\mathcal{O}}_X$. Thus $D\mapsto [{\mathcal{O}}_X(D)]$ induces a group homomorphism from the divisor class group to the Picard group.

For surjectivity, let $\mathcal{L}$ be an invertible sheaf. Trivialize its one-dimensional rational fibre over the function field $k(X)$; equivalently, choose a nonzero rational section and identify $\mathcal{L}$ with a subsheaf of the rational-function sheaf. A finite trivializing cover givesOn overlaps $a_i/a_j$ is a regular unit. The integers $-v_P(a_i)$ therefore agree wherever two descriptions apply and define a finite divisor on an algebraic curve $D$. Its local description gives $\mathcal{L}={\mathcal{O}}_X(D)$. A different rational trivialization multiplies all $a_i$ by the same rational function, changing $D$ by a principal divisor, so the resulting divisor class is intrinsic.

For injectivity, an isomorphism ${\mathcal{O}}_X(D)\to {\mathcal{O}}_X(E)$ becomes multiplication by some $g\in k(X{)}^{\ast }$ on the rational fibre. At each closed point its effect on the local free generators givesHence $D-E=\mathrm{div}(g)$. Conversely this equality gives the required isomorphism by multiplication by $g$. We have proved the group isomorphism

Put $\mathcal{D}={\mathcal{K}}_X^{\ast }/{\mathcal{O}}_X^{\ast }$, the quotient sheaf of abelian groups. At a closed point $P$, the discrete valuation gives an isomorphismIndeed, a local parameter on a smooth algebraic curve has valuation one, and the valuation kernel is precisely the unit group of the discrete valuation ring. Thus a local section represented by $f$ determines its local principal divisor, and changing $f$ by a regular function which is a unit does not change those coefficients.

These local valuations identify $\Gamma (X,\mathcal{D})$ with $\mathrm{Div}(X)$. To see that they give finite support, represent a section locally by finitely many rational functions on an algebraic variety, using Noetherian Zariski topology to take a finite cover. Each representative has only finitely many zeros and poles, so their combined support is finite. Conversely, for $D=\sum n_{P}P$, choose at each support point a local parameter $t_P$ and shrink its neighbourhood to exclude every other zero or pole of $t_P$ and every other support point. The local rational equation $t_P^{n_P}$ represents the desired valuations there; on the complement of the support use $1$. On overlaps these equations differ by units, so their classes glue in the quotient sheaf. Finally, a section with every valuation zero has zero germ everywhere and is the identity section. Hence the identification is both surjective and injective.

The map on global sections sends $f\in k(X{)}^{\ast }$ to $\mathrm{div}(f)$. Therefore its cokernel is

Let $P$ be a sphere with $g+1$ disjoint open disks removed, and form its double $S$ by gluing two copies along the boundary. Then $\chi (S)=2\chi (P)=2(1-g)$, so $S$ is an oriented closed surface of genus $g$. The involution $\iota$ swapping the two halves fixes precisely the $g+1$ seam circles.

Use disjoint collars with coordinates $(s,t)\in \mathbb{R}/\mathbb{Z}\times (-\eta ,\eta )$, where $\iota (s,t)=(s,-t)$. Choose a smooth even bump function $\chi (t)$ supported inside the collar, with $\chi (0)=1$, and choose $0<ϵ<1$. Define an orientation-preserving diffeomorphism $R$ on each collar by $R(s,t)=(s+ϵ\chi (t),t)$ and as the identity outside the collars. Scaling $ϵ$ from zero gives an isotopy from the identity to $R$, so $F=R\circ \iota$ is homotopic to $\iota$.

A fixed point of $F$ in a collar would satisfy $-t=t$, hence $t=0$. Its other coordinate would then require $s+ϵ=s$ modulo one, impossible for the chosen $ϵ$. Outside the collars, $F=\iota$ exchanges the interiors of the halves and has no fixed points. Therefore $\iota$ has fixed circles but is homotopic to the fixed-point-free map $F$. This is the fixed-point-free perturbation of a doubled-surface reflection; the construction includes genus zero, where the double is a sphere.

Take the double cover of $S^2$ branched at $2g+2$ points, with deck involution $\iota$. One explicit construction cuts the sphere along $g+1$ disjoint arcs pairing the branch points and cross-glues two copies along the cuts. Its Euler characteristic is $2\chi (S^2)-(2g+2)=2-2g$, so it is an oriented closed surface of genus $g$. Locally at a branch point the projection is $z\mapsto z^2$ and the involution is $z\mapsto -z$; thus the involution is nonidentity and orientation-preserving, also when $g=0$.

The invariant rational cohomology of a finite surface action identifies with the cohomology of its quotient. For this action, triangulate the quotient with the branch points as vertices and lift the triangulation. Quotient cochains identify with invariant cochains, and averaging over the two deck transformations makes taking invariants exact over $\mathbb{Q}$. Hence the invariant part of $H^1(S;\mathbb{Q})$ is $H^1(S^2;\mathbb{Q})=0$. Since ${\iota }^2=1$, its eigenvalues are $\pm 1$ and it is therefore $-I$ on the $2g$-dimensional $H^1$. Its actions on $H^0$ and $H^2$ are both the identity. ThusHomotopy invariance and the result just proved show that every map homotopic to this involution has fixed points, for every genus.

First prove the concentration statement with its correct scale. Let $U_i=R_i^2$, the $i$th uniform order statistic. The number of sample points at most $z$ is $B_z\sim \mathrm{Bin}(n,z)$. Therefore $U_i>z$ means $B_z<i$, and $U_i<z$ means $B_z\ge i$, up to probability-zero ties. Take ${\epsilon }_n=1/\log n$ and $M=\lceil n^{1/10}\rceil$. Applying Chernoff bounds at $z=(1\pm {\epsilon }_n{)}^{2}i/n$ gives, for an absolute $c_0>0$ and sufficiently large $n$,When the upper endpoint exceeds one its upper-tail event is empty. A union bound makes the total failure probability for all $M\le i\le n$ at most $2n\exp (-c_{0}M/(\log n{)}^2)=o(1)$. On this event,where integral comparison gives ${\sum }_{i=M}^n{i}^{-1/2}=2\sqrt{n}+O(\sqrt{M})$.

The first vertex block has right endpoint $R_1$ and always contains $L_1$, so its initial chord contributes vertex degree two. All its other endpoints are those $L_i$ with $i\ge 2$ that fall below $R_1$. Conditional on the right endpoints, these events are independent with probabilities $R_1/R_i$. ThusThe fewer than $M$ early summands contribute at most $M=o(\sqrt{n})$ to this conditional mean. For the rest, the uniform estimate and uniform tightness of $\sqrt{n}{R}_1$ giveTo control the actual fluctuations without assuming unconditional independence, restrict to the concentration event and $\sqrt{n}{R}_1\le A$. Then $\mu (R)\le M+2+CA\sqrt{n}$. Conditional Chebyshev inequality bounds the probability of a deviation exceeding $\eta \sqrt{n}$ by $(M+2+CA\sqrt{n})/({\eta }^{2}n)=o(1)$. The discarded endpoint event has limiting probability $e^{-A^2}$; let $A\to \infty$. ThereforeSince $W$ has a continuous distribution, the corrected first-vertex degree in the LCD model tail isThis disproves the printed exponent $-y^2/8$ for $G_n^{(1)}$. The hint's factor is independently contradicted at $i=n$: its proposed upper bound tends to $1/\sqrt{2}$, whereasThus the printed concentration event has probability tending to zero, not one. Replacing its $2n$ by $n$ leads to the proven exponent $-y^2/4$. The exponent $-y^2/8$ would instead arise for $d_1(2n)/\sqrt{n}$, but then the graph has $2n$ vertices and the part (b) endpoint limit at $x/\sqrt{n}$ becomes $e^{-2x^2}$. It cannot repair all the printed claims with one convention. The literal part (c) is false for the named model; the full corrected limit and the source of the discrepancy are established above.

The first right endpoint is the smallest of $n$ independent pair maxima. A maximum exceeds $r$ with probability $1-r^2$, so for $0\le x\le \sqrt{n}$,Taking the limit gives the requested, correctly normalized resultThus $\sqrt{n}{R}_1$ converges to a continuous nonnegative limit $W$ with survival function $\mathrm{Pr}(W\ge x)=e^{-x^2}$. In particular the scaled first right endpoint is tight. This calculation uses maxima of pairs, not the first order statistic of all $2n$ individual endpoints, which would have a different scale. The converted TeX loses the formula in this part; the displayed limit has been recovered directly from the PDF.

Draw $n$ independent pairs of independent uniform random variables on $[0,1]$. In each pair call the minimum $L$ and maximum $R$, then relabel whole pairs so $R_1<\cdots <R_n$. Merge all endpoints in $(R_{i-1},R_i]$ into vertex $i$, with $R_0=0$, and join the blocks containing the two endpoints of each pair, orienting from the right endpoint to the left. Self-loops are retained. This gives the uniform linearized chord diagram representation.

Before ordering, a pair has joint density $2$ on $0<L<R<1$. Consequently its maximum has distribution $\mathrm{Pr}(R\le r)=r^2$ and density $2r$; conditional on $R=r$, its minimum is uniform on $[0,r]$. Independence and relabelling give the equivalent precise descriptionEvery one of the $(2n)!$ relative orderings of the independently drawn labelled endpoints has the same probability. After forgetting pair labels and within-pair labels, each matching of $2n$ ordered points is produced by $2^{n}n!$ orderings. Thus its matching is uniform among the $(2n-1)!!$ pairings.

To prove equivalence with the recursive graph law, remove the last endpoint and its mate from a uniform pairing. The remaining ordered points have a uniform $(n-1)$-pairing, and the mate's old rank is uniform among the $2n-1$ possible ranks, independently of that smaller pairing. Conversely insert the mate into a uniformly chosen one of its $2n-1$ gaps, and pair it with the new final endpoint. For each old vertex block, the number of gaps assigned to it is exactly the number of endpoints already in that block, hence its old total vertex degree. These are the gaps immediately before each endpoint of that block. The last gap, after the last old endpoint, makes both new endpoints belong to the new final block and produces a self-loop. Therefore the attachment probabilities are $d_i/(2n-1)$ for old vertices and $1/(2n-1)$ for the new one. Induction proves the continuous construction and the recursive LCD model have the same distribution. Inserting a left endpoint into an old block raises exactly that vertex's vertex degree without splitting any old block.

The necessary and sufficient condition iswhere $\rho$ is the spectral radius of the nonnegative matrix. No irreducibility is required. We use the given nonnegative-vector characterization of its Perron eigenvalue.

For necessity, suppose $p\ne 0$ is the survival fixed point and let $S=\{i:p_i>0\}$. Since $1-e^{-z}<z$ for every $z>0$, its equation gives $(\Lambda p{)}_i>p_i$ for every $i\in S$. There are finitely many such coordinates, soOutside $S$ the inequality $\Lambda p\ge \alpha p$ still holds, because its right side is zero and its left side is nonnegative. The provided Perron–Frobenius theorem characterization therefore gives $\rho (\Lambda )\ge \alpha >1$. In particular survival is impossible at $\rho =1$ for this Poisson offspring law.

Conversely suppose $\rho >1$. The given characterization supplies a nonzero $v\ge 0$ with $\Lambda v\ge \rho v$; normalize it so ${\max }_i{v}_i=1$. For sufficiently small $\eta >0$,For example any $0<\eta \le \min (1,2(\rho -1)/{\rho }^2)$ works. Coordinates with $v_i=0$ satisfy the inequality automatically. Starting at $x_0=\eta v$, iterate $x_{t+1}=T(x_t)$. Monotonicity makes the sequence increase, and $T$ takes nonnegative vectors into $[0,1{]}^l$, so it converges to a fixed point $x_{\infty }\ge \eta v\ne 0$. Part (a) gives $p\ge x_{\infty }$, proving survival from at least one type. This proves the spectral survival criterion for multitype Poisson branching for reducible as well as irreducible reproduction matrices.

Use row vectors for population counts. Given $Z_t$, independent reproduction has conditional mean $\mathbb{E}[Z_{t+1}\mid Z_t]=Z_t\Lambda$. Starting from $Z_0=e_i^T$, induction gives $\mathbb{E}{Z}_t=e_i^T{\Lambda }^t$. Summing all child types, the expected size of generation $t$ isThis also covers $t=0$, using ${\Lambda }^0=I$. All these finite-generation expectations are finite because the matrix is finite with finite entries.

At each vertex independently, take a uniformly random permutation of the other $n-1$ vertices. Use its first two entries for the two-out choices and its first $k$ entries for the $k$-out choices. Every unordered choice set has the prescribed uniform distribution, and choices at different vertices remain independent. This couples the random k-out graphs so that $G_{2\text{-out}}\subseteq G_{k\text{-out}}$ on the same vertex set. Adding edges cannot destroy graph connectivity. ConsequentlyThis establishes connectivity of random k-out graphs for every fixed allowed $k$.

If the random k-out graph with $k=2$ is disconnected, one of its connected components of a graph has size $3\le s\le n/2$. The lower bound follows because every vertex chooses two distinct neighbours inside its component. For a specified $s$-set $S$, absence of crossing edges requires every choice at a vertex in $S$ to stay in $S$, and every choice outside to stay outside. Independence of choices at different vertices gives exactlyFor $3\le s\le n/2$, the two ratios are at most $(s/n{)}^2$ and $(1-s/n{)}^2$. Indeed each of the factors $(s-j)/(n-j)$, $j=1,2$, is at most $s/n$, and the complementary statement is identical. Put $t=s/n$. The binomial coefficient bound $\left(\genfrac{}{}{0ex}{}{n}{s}\right)\le t^{-s}(1-t{)}^{-(n-s)}$ follows by bounding the probability of $s$ successes in $\mathrm{Bin}(n,t)$ by one. Thus the union bound givesFor $s\le \sqrt{n}$, the last summands are at most $n^{-s/2}$, whose sum from three tends to zero. For $s>\sqrt{n}$, they are at most $2^{-s}$, again summing to zero. ThereforeThe proof bounds all possible small components rather than assuming the dependent undirected edges behave like a binomial random graph.

False. Complementary-size simplicial vertex boundaries can be asymmetric. Use $n=7$, $k=63$ and $l=65$, so $k+l=128$.

There are 64 sets of size at most three. The initial segment $C(63)$ contains all of them except the last triple $\{5,6,7\}$. Every four-set has another included triple, so its external vertex boundary is that missing triple together with all $\left(\genfrac{}{}{0ex}{}{7}{4}\right)=35$ four-sets: $|\partial C(63)|=36$.

The initial segment $C(65)$ contains all sets of size at most three and the first four-set $\{1,2,3,4\}$. Its external vertex boundary has the other 34 four-sets and the three five-sets containing $\{1,2,3,4\}$. Thuscontradicting the proposed inequality.

False. The simplicial vertex boundaries need not increase below half volume. In $Q_3$,Both closed graph neighbourhoods consist of all vertices except $\{1,2,3\}$, so both have size seven. Their external vertex boundaries therefore have sizesalthough $3<4=2^{3-1}$. Adding a vertex already in the neighbourhood can reduce the external vertex boundary without enlarging the neighbourhood.

Always true. Simplicial initial segments are nested: $C(k)\subseteq C(l)$ when $k\le l$. Taking the closed graph neighbourhood preserves inclusion, hence $N[C(k)]\subseteq N[C(l)]$ and the claimed size inequality follows. No extremal theorem is needed for this step.

Take $u(z)=\log |z|$. In polar coordinates its Laplacian is $u_{rr}+r^{-1}{u}_r=-r^{-2}+r^{-2}=0$, so it is harmonic on the annulus. If $u=\mathrm{Re}f$ for a single-valued holomorphic function, the Cauchy-Riemann equations would give $f^{\prime }=u_x-i{u}_y=1/z$. But for $1<\rho <2$,The first equality follows by evaluating the primitive $f$ around a closed curve. This contradiction verifies the absence of a global harmonic conjugate.

For the final function, the quotient of squared distances is $|z+1{|}^2/|z-1{|}^2$. On $|z|>1$, both $1+1/z$ and $1-1/z$ lie in the open right half-plane, so their principal logarithms are single-valued and holomorphic. DefineThe series converges locally uniformly outside the unit circle, andThus this is the required single-valued holomorphic function, even on the larger domain $|z|>1$. Its derivative is $2/(z+1)-2/(z-1)$, whose two periods around the holes cancel. The logarithmic cancellation on an exterior annulus explains why this example succeeds while $\log |z|$ fails; using independent multivalued logarithms of $z+1$ and $z-1$ would conceal that cancellation.

For a harmonic function $u$, put $g=u_x-i{u}_y$. Its Wirtinger derivative isso the Cauchy-Riemann equations make $g$ holomorphic. In the simply connected domain it has a single-valued primitiveThe integral is path independent: local holomorphic primitives make its value invariant under path homotopies, and being simply connected makes any two paths with the given endpoints homotopic, as in Question 3.

Since $F^{\prime }=g$, the real part satisfies $(\mathrm{Re}F{)}_x=u_x$ and $(\mathrm{Re}F{)}_y=\mathrm{Re}(ig)=u_y$. Hence $\mathrm{Re}F-u$ is constant on the connected domain. Adding a real constant corrects it, producing a single-valued holomorphic $f$ with $\mathrm{Re}f=u$. The imaginary part is a harmonic conjugate and is unique up to an additive real constant. This is the global harmonic conjugate criterion by vanishing periods in the simply connected case.

The intended construction is to solve the Lenard-Magri recursion one step at a time. With $H_0$ a Casimir function of the first Poisson structure, seek $H_n$ satisfyingHere $X_H^{(a)}f=\{f,H{\}}_a$, consistently with part 1(i). If every step can be solved by a globally defined smooth function, the formal series ${\sum }_{n\ge 0}{H}_n{\lambda }^n$ is a Casimir function for the Poisson pencil, and part (i) proves that all the $H_n$ are Poisson-commuting functions for every parameter value after complexification.

The recursive step is a concrete potential problem. Put $Y=-X_{H_{n-1}}^{(2)}$. It must first be tangent to the symplectic leaves of ${\Pi }_1$. On a regular leaf use canonical coordinates $(q_i,p_i)$. The required equations areThus the leaf one-formmust be exact. Where it is closed on a contractible coordinate domain, define $H_n$ by integrating ${\alpha }_Y$ from a base point; path independence follows from closedness. A function of the leaf labels can be added, corresponding to a Casimir function of the first Poisson structure. Global solvability also requires vanishing periods and smooth matching between leaves. This describes how to perform each solvable step without pretending that a degenerate Poisson structure can simply be inverted.

Compatibility alone does not ensure these solvability conditions. There is an immediate obstruction to a Lenard-Magri recursion even in two dimensions. On $M={\mathbb{R}}^2$ takeBoth are Poisson structures, and their linear combination is a scalar multiple of the canonical Poisson bracket, so they are compatible. Every function, including $H_0$, is a Casimir function for the first bracket. But the first recursion, evaluated at $f=y$, would requirea contradiction. An arbitrary initial Casimir need not extend even to $H_1$. Consequently the unconditional existence assertion requires an additional hypothesis: the indicated vector field must be Hamiltonian for ${\Pi }_1$ at every step. Under that hypothesis the recursive construction and involution proof above complete the intended result; without it the counterexample rules out the requested infinite extension.