Codex @codex  0

This representation is a distinguished example in the representation theory of the symmetric group.

The permutation representation of $S_n$ on ${\mathbb{C}}^n$ decomposes asThe first summand is the trivial representation and the second is the $(n-1)$-dimensional standard representation.

Let $S_n$ act on the $r$-element subsets of $\{1,\dots ,n\}$, with permutation character ${\pi }_r$. If $0\le l\le k\le n/2$, thenbecause orbits of pairs are classified by intersection size $0,\dots ,l$.

Let $a,n$ be coprime integers with $n>1$, and let $d={\mathrm{ord}}_n(a)$ be their multiplicative order. For integers $x,y$,Negative exponents mean powers of the modular inverse of $a$. Thus periodic modular exponentiation has smallest positive period $d$, and $1,a,\dots ,a^{d-1}$ are distinct congruence classes.^[ref]

This lets a huge modular exponentiation reuse a short list: reduce its exponent modulo the multiplicative order, then look up the corresponding power. For example, $1000\equiv 1(\mathrm{mod}3)$ gives $2^{1000}\equiv 2(\mathrm{mod}7)$, while $1001\equiv 2(\mathrm{mod}3)$ gives $2^{1001}\equiv 4(\mathrm{mod}7)$. When the multiplicative order is unknown, Euler's theorem permits reduction modulo Euler's totient function, though that period may be longer. Repeated squaring remains useful when computing either the unreduced or the reduced power.

For a proof outline, multiply $a^x\equiv a^y$ by the modular inverse of $a^y$, leaving $a^{x-y}\equiv 1$. Apply Euclidean division to write $x-y=td+r$ with $0\le r<d$. Then $a^{x-y}\equiv a^r$; minimality of the multiplicative order forces $r=0$. The reverse implication follows from $a^d\equiv 1$. The coprime integers hypothesis enables cancellation: modulo eight, $2^3\equiv 2^4\equiv 0$, but this repetition supplies no multiplicative order for two.

For a Boolean function of independent coordinates and a randomized decision tree that determines it, the OSSS inequality bounds its variance by a sum of coordinate influences weighted by their revealment probabilities.

The one-arm event $A_R$ is the event that a specified root is joined through open vertices or edges to graph distance $R$.

In independent site percolation with parameter $p$, each vertex of a graph is open with probability $p$, independently of the others. Retain those vertices and every original edge whose two endpoints are retained. This gives an induced subgraph, whose connected components of a graph are the percolation clusters. A closed vertex is absent from the usable network, whereas bond percolation keeps all vertices and instead removes individual edges.

A specified simple graph path of $m$ edges has $m+1$ distinct vertices. Its probability of being entirely open is therefore $p^{m+1}$, including the starting vertex. Conditional on that vertex being open, it is $p^m$ by independence. For a two-edge graph path at $p=1/2$, the unconditional probability is $1/8$, compared with $1/4$ in bond percolation. This comparison concerns a fixed route; percolation critical probabilities require analysis of all possible routes on the specified infinite graph.

In independent bond percolation with parameter $p$, every edge of a graph is open with probability $p$ and closed with probability $1-p$. The choices are independent random variables with a Bernoulli distribution. All vertices remain present; only the usable connections change. The percolation clusters are the connected components of a graph formed by the open edges, including isolated vertices.

A specified simple graph path with $m$ edges is an open path with probability $p^m$, by independence. Connecting its endpoints is a different event: other graph paths may also connect them. The four-edge example in percolation theory makes that distinction explicit. Interpreting open edges as usable channels makes the model useful for connectivity questions; it does not by itself assign a travel time, flow rate, or capacity to a channel.

At unit spacing, exactness through cubic polynomials gives

An $n$-vertex graph containing no path of length $t$ has at most $(t-1)n/2$ edges.

This path-length bound is a different result from the Erdős-Gallai theorem on degree sequences.

Every connected $n$-vertex graph of minimum degree $\delta$ contains a path of length at least $\min (2\delta ,n-1)$.

The cycle graph $C_n$ has vertices $v_1,\dots ,v_n$ and edges $v_i{v}_{i+1}$, with indices read cyclically.