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.
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…
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
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,
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
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 …
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.
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…
Random Graphs with a Given Degree Sequence 2: The Closure of the β-Model Expected Degree Sequences Equals the Convex Hull of All Degree SequencesResearch Paper
A degree sequence records how many neighbours each vertex of a graph has. In network statistics it is often the only summary of a graph that is observed or trusted, and the natural probability models for graphs in which "the degree sequence captures the information" are exponential families whose sufficient statistic is the degree sequence. Chatterjee,…
Graph Minors. X. Obstructions to Tree-Decomposition IV: Mutually Distinguishable Tangles Have a Tree-Decomposition Separating Them by Their DistinctionsResearch Paper
Robertson and Seymour introduced tangles in Graph Minors. X (J. Combin. Theory Ser. B 52 (1991) 153–190) as the precise obstruction to tree-decompositions of small width: a graph has a tangle of large order exactly when it has no tree-decomposition of small width. A tangle points to a highly connected region of a graph without naming its vertices, by…