Research, experiments, and short notes.
Exact maximum variance bounds for random-order greedy independent-set size on split graphs and cographs, with a unique extremizer in each class. The draft also gives a stability result and a counterexample for general graphs. Independent proof review and a broader prior-art assessment remain open.
A five-observation counterexample showing that replacing binary outcomes with conditional means can change a calibrated forecast-aggregation problem. Three experts force every outcome, while the relaxation guarantees only three correct predictions. The note proves minimality and extends the result to calibration error and repeated observations.
When a random quantity counts events, write it as a sum of indicators. The variance then separates into individual uncertainty and pairwise dependence.
Here X = ∑v Iv and pv = P(Iv = 1). The pairwise terms vanish only when the indicators are pairwise independent.
For any nonnegative integer-valued random variable X, count one unit for every threshold X reaches:
For each outcome, X = ∑k≥1 1{X ≥ k}. Taking expectations gives the identity. It is often easier to bound the chance of reaching each threshold than to find the full distribution.
Hao Huang's proof of the sensitivity conjecture starts by giving some hypercube edges weight −1. The signed adjacency matrices are built recursively:
The negative block cancels the cross terms when the matrix is squared. Induction gives:
Since the trace is zero, each eigenvalue occupies half the spectrum. Keep any set of more than half the hypercube's vertices. Eigenvalue interlacing forces the corresponding principal submatrix to have an eigenvalue at least √n. Its maximum absolute row sum bounds that eigenvalue, so some retained vertex has at least √n retained neighbors.
The useful move is to preserve where a matrix is nonzero while choosing signs that force a simple spectrum. This construction helped settle the sensitivity conjecture in 2019.
For a scalar function f analytic near the spectrum of A, its matrix function has a directional derivative Lf(A, E) = d/dt f(A + tE)|t=0. Place E in the upper-right block of a larger matrix:
The derivative appears in the same corner. The upper-right block of the kth power is ∑j=0k−1 AjEAk−1−j, exactly the derivative of Ak. Power series extend the identity to analytic functions.
Squaring gives AE + EA, correctly accounting for noncommutativity. For the matrix exponential:
This turns differentiation into function evaluation, useful for sensitivity analysis and optimization involving matrix functions. Exploiting the block structure reduces the overhead of the larger matrix.
Wiedemann's algorithm solves linear systems over finite fields using matrix-vector products. Given an invertible n × n matrix A and a vector b, choose a random vector u and record:
The scalar sequence obeys a linear recurrence. Berlekamp–Massey recovers its shortest recurrence from the first 2n terms. A projection can miss factors, so the resulting polynomial must be checked and additional projections may be needed.
Once a polynomial p(t) = td + cd−1td−1 + ⋯ + c1t + c0, with c0 ≠ 0, is verified to satisfy p(A)b = 0, the solution to Ax = b follows:
Multiplying by A recovers b directly from the polynomial identity. The trick compresses matrix dynamics into a recurrence, then uses it to apply an inverse without storing a dense inverse or factorization.
The permanent is the determinant's permutation sum with every sign replaced by a plus. For a 0/1 bipartite adjacency matrix, it counts perfect matchings. MacMahon's Master Theorem gives an unexpected way to encode it:
Here X = diag(x1, …, xn), and the brackets extract a coefficient from the formal power series. For a 2 × 2 matrix A with rows (a, b) and (c, d), the denominator is:
The coefficient of xy in its reciprocal is ad + bc. Taking the reciprocal converts the signed determinant information into unsigned permutation counts.
This is useful for translating counting problems into generating functions. It does not make general permanent computation easy: extracting the multivariate coefficient carries the difficulty.
Over the field 𝔽p, for prime p, xp−1 equals 0 when x = 0 and 1 otherwise. Exponentiation becomes a selection switch. Combined with Chevalley–Warning, this proves that any 2p − 1 integers contain exactly p entries whose sum is divisible by p.
Given the integers ai, impose two equations over 𝔽p:
The sum of their degrees is at most 2p − 2, smaller than the number of variables. Chevalley–Warning says the number of solutions is divisible by p. Since the all-zero solution exists, it cannot be the only one.
In a nonzero solution, the number of selected indices is a positive multiple of p. There are fewer than 2p indices, so exactly p are selected. The second equation gives their zero sum.
The reusable move is to encode selection using powers, then force existence through divisibility of the solution count.