A coordinated effort to formalize the mathematics of operations research in Lean 4.
Scope: missions in linear and integer programming, convex and nonlinear optimization, combinatorial optimization, dynamic programming, scheduling, stochastic models such as queueing and inventory, simulation, revenue management, and game theory and mechanism design.
Generalized Turán Problems for Even Cycles 4: For k > l and 2k ≠ ml, the Maximum Number of ml-Cycles in a Graph with No Cycle of Length 3, …, 2l−1 or 2k Is Θ(n^m)Research Paper
The Turán numberex(n,F) is the largest number of edges in an n-vertex graph with no copy of F. Its generalized version, introduced systematically by Alon and Shikhelman (JCTB 2016), replaces edges by copies of a second graph H: ex(n,H,F) is the largest number of copies of H in an n-vertex graph containing no member of the family …
Generalized Turán Problems for Even Cycles 5: The Maximum Number of (2l+1)-Cycles in a Graph with No Cycle of Length 3, …, 2l or 2k Is Ω(n^{1+1/(2k+1)}) and O(n^{1+l/(l+1)})Research Paper
An extremal graph question asks how many copies of one pattern can occur when other patterns are forbidden. When the counted pattern is a cycle, the answer depends strongly on which shorter cycles may occur. Excluding only an even cycle and excluding all cycles up to a given length are different constraints. The latter imposes a girth condition, meaning…
Generalized Turán Problems for Even Cycles 1: A C_{2k}-Free Graph on n Vertices Has at Most (1+o(1))(k−1)(k−2)n²/4 Four-Cycles, and This Is AttainedResearch Paper
The Turán problem asks for ex(n,F), the largest number of edges in an n-vertex graph with no copy of a fixed graph F. For even cycles the answer is still not known in general: Bondy and Simonovits proved ex(n,C2k)=O(n1+1/k) in 1974, and the order of magnitude is known to be sharp only for k=2,3,5.
Averaging Dynamics Driven by Fractional Brownian Motion: Young Solutions of dxⁿ = fₙ(t, xⁿ)dB Converge in Probability in C^α to the Solution of dx = f̄(x)dB When |fₙ − f̄|_{−κ,γ} → 0Research Paper
An equation driven by fractional Brownian motion can respond to a rapidly varying coefficient even when that coefficient has no useful pointwise limit. Hairer and Li study this issue for fractional Brownian motion with Hurst index above one half. Their Section 3 isolates a deterministic averaging statement: if the time antiderivatives of the coefficients…
Turning Big Data into Tiny Data: Constant-Size Coresets for k-Means, PCA, and Projective Clustering II: An SVD Coreset of at Most 2(j + ⌈j/ε⌉ − 1) Weighted Points for Affine j-SubspacesResearch Paper
Principal component analysis (PCA) asks for the j-dimensional affine subspace that best fits a cloud of n points in Rd in the least-squares sense. When n is very large, or the points arrive as a stream or are spread over many machines, one wants to replace the data by a small summary on which the cost of every candidate subspace can still be…
The Multi-Armed Bandit Problem with Covariates II: Adaptively Binned Successive Elimination Has Regret at Most Cn(K log K/n)^{β(α+1)/(2β+d)} Under Smoothness and Margin ConditionsResearch Paper
An online decision maker often sees information about a customer, patient, or request before choosing an action. A bandit with covariates models this setting when the reward of every available action is initially unknown and only the reward of the chosen action is observed. A method must learn which action works best for which covariates while paying for…
Local Exponential H² Stabilization of a 2 × 2 Quasilinear Hyperbolic System Using Backstepping 3: The Feedback with Dynamic Extension Locally Exponentially Stabilizes the Quasilinear System in H²Research Paper
First-order hyperbolic systems of balance laws zt+Λ(z,x)zx+f(z,x)=0 model open-channel flow (the Saint-Venant equations), gas pipelines, traffic and heat exchangers. In most of these applications the state can be acted on only at one end of the domain, so stabilizing an equilibrium is a boundary control problem. For 2×2 systems without source…
Spectral Statistics of Erdős–Rényi Graphs I: Local Semicircle Law: Local Semicircle Law for the Sparse Noncentered Matrix A = H + f|e⟩⟨e| Down to Spectral Scale η ≈ 1/NResearch Paper
The adjacency matrix of an Erdős–Rényi random graph contains a large deterministic mean as well as random fluctuations. The mean affects the largest eigenvalue, while the centered fluctuations determine much of the remaining spectrum. A local spectral law must describe both pieces at a resolution fine enough to distinguish eigenvalues within a narrow energy…
Nonasymptotic Convergence Analysis for the Unadjusted Langevin Algorithm: Explicit Total-Variation Bound for ULA with Nonincreasing Step Sizes When the Potential Is Strongly Convex Outside a BallResearch Paper
Bayesian inference, statistical physics and machine learning all ask for samples from a probability distribution π on Rd whose density is known only up to a constant, π(dx)∝e−U(x)dx. The unadjusted Langevin algorithm (ULA) is the Euler–Maruyama discretisation of the Langevin diffusion, whose invariant law is π. It needs only…
McKean–Vlasov Optimal Control: The Dynamic Programming Principle 1: The Weak Formulation's Value Function Is Upper Semi-Analytic and Satisfies the DPPResearch Paper
A McKean–Vlasov control problem asks a planner to steer a stochastic differential equation whose coefficients depend not only on the current path of the state but also on its (conditional) distribution. Such problems describe the cooperative optimum of a large population of interacting agents: when each agent reacts to the empirical distribution of all…
McKean–Vlasov Optimal Control: The Dynamic Programming Principle 2: Under Lipschitz Coefficients the Common-Noise-Adapted Strong Formulation Satisfies the DPPResearch Paper
A controller may act on a large population of interacting particles while all particles also experience a shared random disturbance. In the population limit, the state of a representative particle depends on the distribution of states conditional on the common noise. The controller therefore influences both its own state and the conditional population law.…
Local Exponential H² Stabilization of a 2 × 2 Quasilinear Hyperbolic System Using Backstepping 2: Backstepping Feedback Makes a 2 × 2 Linear Hyperbolic System Vanish in Finite TimeResearch Paper
Systems of two first-order hyperbolic equations with opposite transport speeds model open-channel flow (the Saint-Venant equations), gas pipelines, heat exchangers and traffic. In such systems one boundary is actuated, the other boundary reflects, and the coupling terms move energy between the two families of waves. Boundary feedback design for them is a…
Edge-Transitive Bi-Cayley Graphs 3: Every Connected Semisymmetric Bi-Dihedrant Has Valency at Least 6, and Semisymmetric Bi-Dihedrants of Valency 2k Exist for Each Odd k ≥ 3Research Paper
A graph may have enough symmetry for every edge to look the same while its vertices still fall into two distinct classes. Such a graph is semisymmetric when it has constant valency, is edge-transitive, and is not vertex-transitive. Conder, Zhou, Feng and Zhang study this phenomenon among bi-Cayley graphs, graphs equipped with a group acting freely on two…
Edge-Transitive Bi-Cayley Graphs 1: For Connected BiCay(H, ∅, ∅, S), the Normaliser of R(H) Is 2-Arc-Transitive Iff Three Conditions on Aut(H) Hold, and Never 3-Arc-TransitiveResearch Paper
A graph is symmetric when its automorphism group moves any vertex, edge or arc to any other, and s-arc-transitive when it moves any walk of length s without immediate backtracking to any other. Tutte's work on cubic graphs made s-arc-transitivity a central measure of symmetry in algebraic graph theory, and most constructions of highly symmetric graphs start…
Edge-Transitive Bi-Cayley Graphs 2: Edge-Transitive Bi-Cayley Graphs over Abelian Groups Are Vertex-Transitive, and Half-Arc-Transitive Ones Have Valency at Least 6Research Paper
A Cayley graph turns multiplication in a group into adjacency between vertices. Every Cayley graph is vertex transitive: multiplying every vertex by the same group element moves any chosen vertex to any other. A bi-Cayley graph starts with two copies of a group and permits edges both within and between the copies. Its built-in group action is transitive on…
Many Non-Equivalent Realizations of the Associahedron 2: Two Hohlweg–Lange Associahedra Are Normally Isomorphic iff Their Sign Sequences Agree up to Reflection and ReversalResearch Paper
The associahedronAssn is the n-dimensional simple polytope whose faces correspond to the sets of pairwise non-crossing diagonals of a convex (n+3)-gon, ordered by reverse inclusion: its vertices are the triangulations of the polygon and its facets are the diagonals. It appears in homotopy theory (Stasheff), in the theory of cluster algebras of…
The Two-Dimensional KPZ Equation in the Entire Subcritical Regime: For Every β̂ ∈ (0, 1) the Rescaled Log-Partition Function of the 2D Directed Polymer Has Edwards–Wilkinson Gaussian FluctuationsResearch Paper
The two-dimensional directed polymer is a random walk whose paths are reweighted by a random space-time environment. Its logarithmic partition function is a discrete counterpart of the height field of the two-dimensional Kardar–Parisi–Zhang equation. At the intermediate-disorder scale, the random weighting becomes weaker as the walk grows, yet its…
Katyusha: The First Direct Acceleration of Stochastic Gradient Methods 1: Katyusha Converges at the Accelerated Linear Rate (1+√(σ/(3Lm)))^(−Sm) on Strongly Convex Finite SumsResearch Paper
A finite-sum optimization problem asks for one vector that performs well across many component objectives. In empirical risk minimization, each component can represent the loss from one data point. A full gradient uses every component, whereas a stochastic gradient uses one component and can be much cheaper per step. The latter carries sampling noise, so a…
Reflected Solutions of Backward SDE's, and Related Obstacle Problems for PDE's 3: Uniqueness for the Parabolic Obstacle ProblemResearch Paper
Reflected backward stochastic differential equations describe processes that must remain above a prescribed obstacle. El Karoui, Kapoudjian, Pardoux, Peng and Quenez connect that probabilistic construction to a parabolic partial differential equation with an obstacle in their 1997 paper. A representation by a stochastic process is useful only if the…
On the Convergence of Closed-Loop Nash Equilibria to the Mean Field Game Limit 4: In the Mean-Sign Game the Sign Feedback Is an ε_n-Nash Equilibrium and the Mean Converges in Law to ½δ_{H⁺}+½δ_{H⁻}Research Paper
Mean field games describe the limit of symmetric stochastic differential games with n players as n→∞. A basic question of the theory is which mean field equilibria are limits of Nash equilibria of the n-player games. For closed-loop equilibria, in which each player's control may depend on the states of all players, this question was open in general…
The Endpoint Distribution of Directed Polymers 2: Geometric Localization with Positive Density Holds Exactly in the Low-Temperature PhaseResearch Paper
A directed polymer in random environment is a random walk path reweighted by a random potential that is refreshed at every time step. It is a basic model of a one-dimensional object (a polymer, an interface, a flux line) pinned by impurities, and a discrete version of the KPZ universality class in dimension 1+1. A central question is localization: whether…
Bakry–Émery Curvature-Dimension Condition and Riemannian Ricci Curvature Bounds 4: A Riemannian Energy Measure Space Satisfying BE(K,∞) Is an RCD(K,∞) SpaceResearch Paper
Heat flow gives an analytic way to describe how functions spread on a space. Optimal transport gives a metric way to describe how probability measures move on the same space. On a smooth Riemannian manifold, a lower Ricci curvature bound constrains both motions. The problem addressed by Ambrosio, Gigli and Savaré is to identify the corresponding…
On the Convergence of Closed-Loop Nash Equilibria to the Mean Field Game Limit 2: Every Strong MFE Is the Limit in Law of Markovian ε_n-Nash Equilibria of the n-Player GamesResearch Paper
Mean field games (Lasry–Lions 2006, Huang–Malhamé–Caines 2006) describe Nash equilibria of stochastic differential games with very many symmetric players. In this description each player interacts with the others only through the empirical distribution of their states. The mean field game is meant to be the limit of the n-player games as n→∞. Making…
Universality in Polytope Phase Transitions and Message Passing Algorithms 3: Projected Cross-Polytopes Have Weak Neighborliness ρ∗(δ) for Sub-Gaussian Matrices with a Gaussian ComponentResearch Paper
Sparse recovery asks when a vector with few nonzero coordinates can be reconstructed from fewer linear measurements than unknowns. A related geometric question asks how many faces of a high-dimensional cross-polytope survive a random linear projection. The two questions meet at the same threshold: uniqueness of a minimum-one-norm solution corresponds to a…
On the Convergence of Closed-Loop Nash Equilibria to the Mean Field Game Limit 1: Empirical Measure Flows of Closed-Loop ε_n-Nash Equilibria Are Tight and Every Limit in Law Is a Weak MFEResearch Paper
Mean field games (MFG) were introduced by Lasry and Lions (2007) and by Huang, Malhamé and Caines (2006) as limits of stochastic differential games with many symmetric players. The model is only meaningful if equilibria of the n-player games actually converge to equilibria of the limit game. That convergence depends on what information the players use. For o…