The mathematics of finite and discrete structures — counting the arrangements of a set, deciding when a configuration meeting prescribed constraints can exist, and characterizing the patterns such structures are forced to contain. It encompasses enumerative and extremal combinatorics, graph theory, design theory, and additive combinatorics, with deep ties to algebra, probability, and computer science.
Randomness-Efficient Robust Locally Testable Codes in the Low-Acceptance Regime from HDXsResearch Paper
A locally testable code (LTC) is an error-correcting code C⊆Σn with a randomized test that reads few coordinates of a word f and rejects with probability that grows with the distance of f from C. LTCs are a core ingredient of probabilistically checkable proofs and of property testing. The usual guarantee is in the high-acceptance regime: if…
Characterizing Local Breadth in Language GenerationResearch Paper
An algorithm sees an unknown language one string at a time and must produce new strings of that language. Language generation in the limit, introduced by Kleinberg and Mullainathan (2024), models this as a game. The target is any member of a countable candidate family, an adversary enumerates it, and the algorithm must eventually output only unseen strings…
Weighted Set Cover with Constant Worst-Case Recourse: From Exponential to Best-Known Update TimeResearch Paper
In fully dynamic weighted set cover, a fixed family of sets with positive costs is given once, and elements of the universe are then inserted into and deleted from an active set. After every update an algorithm must hold a subfamily that covers the active elements at nearly minimum cost. Besides the approximation ratio, two resources are measured per…
Spatial sorting and the geometry of lattice spin systems at fixed magnetizationResearch Paper
Programmable matter and self-organizing particle systems ask a population of simple agents with a fixed inventory to sort itself into regions by type. A standard way to analyse such algorithms is to model the configurations with a spin system and to run a Markov chain whose stationary law is its Gibbs distribution. Conservation of particles then becomes a…
104 thms1 active userReviewed
Captain: utkuokur
Ten Challenges 02: Excluded minors for GF(pm)-representable matroidsOpen Problem
A matroid records which subsets of a finite set are independent, in the way that sets of columns of a matrix are linearly independent or sets of edges of a graph are acyclic. The matroids that come from matrices over a field F are the F-representable matroids, and deciding which matroids are representable over a given finite field is one of…
Exact directed L/X diameter of the symmetric groupResearch Paper
A generating set determines more than which permutations can be expressed: it also
determines the cost of expressing them. For a finite group, the largest shortest
word length measures how far a generating set is from giving uniformly short
representations. This question connects permutation groups with the distances of
Cayley graphs. Here the generating…
Resistant Sets in the Unit Hypercube: Up to Isomorphism, Rk,1 (k≥1) and R5 Are the Only Half-Dense Strictly Non-Polar Resistant SetsResearch Paper
A clutter is a family of subsets of a finite ground set none of which contains another. A clutter is ideal if its set covering polyhedron {x≥0:∑i∈Cxi≥1 for every member C} has only integral vertices. It packs if the largest number of pairwise disjoint members equals the smallest number of elements meeting every member. Ideal…
Combinatorial Optimization (Cook et al.) X: Every Rational Polytope Has Finite Chvátal RankTextbook
Integer programming asks for the best integral point of a polyhedron, and the standard way to attack it is to describe the convex hull of those integral points by linear inequalities. A simple rule produces such inequalities: if c is an integral vector and cTx≤d holds on a polyhedron P, then cTx is an integer at every integral point of P, so …
21 thms1 active userReviewed
🏆Completed
Captain: FormallyCorrect
Analytic CombinatoricsTextbook
Philippe Flajolet and Robert Sedgewick's Analytic Combinatorics is the standard reference for counting discrete structures exactly and asymptotically. Its methods are used throughout the analysis of algorithms, random structures and enumerative combinatorics. This mission collects formally verified versions of the book's chapter-level results in one…
375 thms1 active userReviewed
Captain: Ethan Cheung Wang
Erdos 624Open Problem
Erdős Problem 624 (erdosproblems.com/624) is a problem of Erdős and Hajnal about how few elements of a set can be enough to "see" the whole set through a function on its subsets. For a finite set X with ∣X∣=n, let H(n) be the least m for which some map f:P(X)→X has the following property: for every Y⊆X with ∣Y∣≥m,
An Invitation to q-Series: Ramanujan's Partition IdentityTextbook
A partition of a nonnegative integer is a way to express it as a sum of positive integers, with the order of the summands ignored. For example, the partitions of 4 are 4, 3+1, 2+2, 2+1+1, and 1+1+1+1. If p(n) denotes their number, then p(4)=5 and p(0)=1, with the empty partition counted once. Although this definition is elementary, the values of p(n) obey…
Erdős #195: monotone 4-term APs in permutations of ZOpen Problem
A permutation of Z in the sense of Erdős and Graham is a one-sided arrangement a0,a1,a2,… in which every integer appears exactly once. Erdős Problem 195 (erdosproblems.com/195) asks for the largest k such that every such arrangement contains a monotone k-term arithmetic progression: indices i1<⋯<ik for which …
Rational Semistandard Tableaux and Character Formula for the Lie Superalgebra ĝl∞|∞: A Jacobi–Trudi Determinant Formula for the Characters of A/B-Semistandard TableauxResearch Paper
The Lie superalgebra gl∞∣∞, a central extension of the Lie superalgebra of infinite matrices of finite support, appears in the representation theory of the W1+∞ vertex algebra and in Howe-type dualities with gln (Kac–Radul; Cheng–Lam). Its irreducible quasi-finite highest weight modules of positive…
Conditional Uniformity and Hawkes Processes: Given Its Size, a Hawkes Cluster's Compensator Points Are ρ Times the Order Statistics of a Uniform Random Parking Function Minus i.i.d. UniformsResearch Paper
Hawkes processes are point processes in which every event raises the rate of future events. They are used to model contagion in financial markets, earthquake aftershocks, the spread of posts on social networks and arrivals to service systems (Hawkes 1971; Hawkes and Oakes 1974). Hawkes and Oakes showed that a stationary Hawkes process is a Poisson stream of…
10 thms1 active userReviewed
Captain: @bwdaugherty
Zero-Core Theorem for Ramsey R(5,5)Research Paper
The Zero-Core Theorem establishes a fundamental structural property of Ramsey graph colorings: the obstruction preventing extension of the champion R(5,5) coloring from n=43 to n=44 is fully distributed across all constraints, with no individual bottleneck.
1 thm1 active userReviewed
🏆Completed
Captain: Yuxuan Xu
Angel-Devil: Complete Integer-Power ClassificationResearch Paper
The Angel problem asks whether bounded movement can overcome an adversary that destroys one square per turn on an infinite chessboard. It is a question about strategies for arbitrarily long play, rather than about finding a path through one fixed configuration. The Devil may act anywhere on the board, including far ahead of the Angel. The movement range…
Continuous graph homomorphisms for Zd-actions: Theorem 1.4 and Proposition 7.1Research Paper
A graph homomorphism sends vertices of one graph to another while preserving adjacency. Requiring this map to be continuous makes graph coloring sensitive to topology: each color must occupy an open and closed region. For integer lattice actions, the resulting questions connect finite graph structure with continuous dynamics. The results considered here…
17 thms1 active userReviewed
Captain: @bwdaugherty
R(5,5) ≥ 43 via GF(p) Polynomial SeedingResearch Paper
The Ramsey number R(5,5) has remained open since the 1960s. The best known bounds are 43 ≤ R(5,5) ≤ 48, where the lower bound was first established by Exoo (1989) via computational search. This mission formalizes an independent verification using novel GF(p) polynomial seeding.
The Running Intersection Relaxation of the Multilinear Polytope 3: Running Intersection Inequalities Meeting Three Support Conditions Define Facets of the Multilinear PolytopeResearch Paper
Binary polynomial optimization asks for the maximum of a polynomial over {0,1}n. Linearizing each monomial ∏v∈ezv by a new variable ze turns the problem into a linear program over the convex hull of a set of 0/1 points, the multilinear polytope of the hypergraph whose edges are the monomials. Global solvers such as BARON build polyhedral…
Stability Results on the Circumference of a Graph 1: A 2-Connected Graph with More Than (⌊c/2⌋−1)(n−c) Edges Off a Longest Cycle of Length c ≥ 10 Lies in W_{n,⌊c/2⌋,c} or (c Odd) in X_{n,c} ∪ Y_{n,c}Research Paper
The circumferencec(G) of a graph G is the length of a longest cycle. Extremal graph theory asks how many edges force a long cycle. The Erdős–Gallai theorem (1959) states that every n-vertex graph has at most c(G)(n−1)/2 edges. Bondy (1971) strengthened it by counting only the edges near a longest cycle: if C is a longest cycle of length c, the number of…
Algorithms for #BIS-Hard Problems on Expander Graphs 2: On Bipartite α-Expanders, the High-Fugacity Hard-Core Partition Function Reduces to Two Kotecký–Preiss Polymer ModelsResearch Paper
The hard-core model on a finite graph G at fugacityλ>0 weights each independent set I of G by λ∣I∣. Its normalizing constant, the independence polynomialZG(λ), is a basic object of statistical physics (a lattice gas with hard-core exclusion) and of combinatorics (ZG(1) counts independent sets).
Algorithms for #BIS-Hard Problems on Expander Graphs 1: On α-Expanders of Maximum Degree Δ, the Low-Temperature Potts Partition Function Reduces to a Kotecký–Preiss Polymer ModelResearch Paper
The ferromagnetic Potts model assigns a larger weight to a coloring when more adjacent vertices have the same color. Computing its partition function is an approximate counting problem with connections to statistical physics and counting complexity. For three or more colors, Goldberg and Jerrum established #BIS-hardness of approximation on general graphs,…
A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem: The Asymmetric Held–Karp Relaxation Has Integrality Gap at Most 319Research Paper
The asymmetric traveling salesman problem (ATSP) asks for a shortest closed walk through every vertex of a directed graph whose edge weights need not be symmetric. It models routing with one-way streets, scheduling with sequence-dependent setup times, and many other problems in which the cost of going from u to v differs from the cost of going back. Its…
Generalized Turán Problems for Even Cycles 3: The Maximum Number of Six-Cycles in a Bipartite C_8-Free Graph on n Vertices Is n³ + O(n^{5/2})Research Paper
The generalized Turán numberex(n,H,F) is the largest number of copies of a graph H in an n-vertex graph containing no member of a family F. With H=K2 it is the classical Turán number; the systematic study of general H began with Alon and Shikhelman (2016), and cycles are its most studied case: Bollobás and Győri bounded …
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 …