Sharp quadratic loads on stars
Abstract
The star has explicit optimal quadratic shares and an explicit maximizing probability vector. Its value also bounds every finite graph from below through its maximum degree.
For an integer m at least one, let H(m) be the simple star on Option(Fin(m)), with centre none and leaves some(i). Write s for the positive square root of m and t for 1/(1+s). The allocation a(m)(b,c) is t when b is the centre and 1-t otherwise. These formulas also bound the irrelevant nonedge coordinates. The probability vector mu(m) assigns t to the centre and 1/(s(1+s)) to every leaf. The function Phi(m) sums p(b)p(c)/(p(b)+p(c)) once over each unordered edge. Real division assigns zero when both coordinates vanish. The simplex contains every nonnegative vector of total mass one, including vectors with zero coordinates.
Theorem 1.1 (Every graph contains the maximum-degree obstruction).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/Graph/QuadraticLoad/StarExtrema.maximum_degree_lower_bound (✓ std3). ∎
Source. Repository-derived.
Commentary.
Take an actual minimum allocation and a vertex b of maximum degree D. Set s equal to the square root of D and t equal to 1/(1+s). For each neighbour c, the complementary shares x and 1-x satisfy sxx+(1-x)(1-x) at least st: their difference is (1+s)(x-t)^2. Summing gives Dst at most s times the load at b plus the sum of the loads at its neighbours. The latter is at most (s+D) times kappa. Cancellation gives D/(1+s)^2 at most kappa. Additional edges among the neighbours only add nonnegative squares to their loads; neither connectivity nor regularity is required.
Theorem 1.2 (Both attained extrema on every star).
Proof. Machine-checked in Lean as D5/S3/Combinatorics/Graph/QuadraticLoad/StarExtrema.star_extrema (✓ std3). ∎
Source. Repository-derived.
Commentary.
The centre load is mtt, and each leaf load is (1-t)^2=mtt. This allocation gives the upper bound, while the maximum-degree estimate gives the reverse bound. The displayed measure has mass one and gives tt on every edge. For any nonnegative competing masses x and y, xy/(x+y) is at most xtt+y(1-t)^2. When x+y is positive, clearing the denominator leaves the square (xt-y(1-t))^2; at x=y=0 both sides vanish. Summing over the m edges bounds every competing probability vector by q(m). Thus both extrema are attained on their full carriers. For m=1 the value is one quarter; for m=2 it is 2(3-2*sqrt(2)). These conclusions alone do not establish growth or legal-word bounds.