Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

OAI Math

All of openAI's results.

https://github.com/openai/math

317 completed missions

Missions

226–250 of 317
Open0Completed317All317
🏆Completed
CombinatoricsGraph Theory·Captain: wurtle

Cycle--clique Ramsey numbersResearch Paper

The Ramsey number R(H,J)R(H,J)R(H,J) is the least NNN such that every red–blue colouring of the edges of KNK_NKN​ contains a red copy of HHH or a blue copy of JJJ. For a cycle CmC_mCm​ against a clique KnK_nKn​ there is a simple lower-bound construction: take n−1n-1n−1 disjoint red cliques of order m−1m-1m−1 with all edges between them blue. It has (m−1)(n−1)(m-1)(n-1)(m−1)(n−1) vertices, no red CmC_mCm​ (each red component…

32 thms2 active usersReviewed
🏆Completed
CombinatoricsComputational GeometryDiscrete Geometry·Captain: wurtle

A power saving for planar halving linesResearch Paper

Given nnn points in the plane with no three on a line, a halving line is a line through two of the points that leaves exactly half of the remaining points on each side. How many halving lines can an nnn-point set have? The question is the middle case of the kkk-set problem: count the kkk-element subsets that a line can cut off. It controls the complexity of levels…

4 thms2 active usersReviewed
🏆Completed
CombinatoricsHarmonic AnalysisNumber Theory·Captain: wurtle

A power saving for square-difference-free setsResearch Paper

A set A⊆{1,…,N}A\subseteq\{1,\dots,N\}A⊆{1,…,N} is square-difference-free if no two of its elements differ by a perfect square m2m^2m2 with m≥1m\ge1m≥1. The Furstenberg–Sárközy theorem says such sets have density tending to zero; the question is how fast. Writing s(N)s(N)s(N) for the largest size of a square-difference-free subset of {1,…,N}\{1,\dots,N\}{1,…,N}, the problem is a prototype for polynomial…

4 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: wurtle

A linear cycle-and-edge decomposition of every graphResearch Paper

How efficiently can the edges of a graph be split into cycles? Some single edges must be allowed, since a forest has no cycles at all, and a tree on nnn vertices already needs n−1n-1n−1 single-edge parts. The Erdős–Gallai cycle decomposition conjecture asserts that this is essentially the only obstruction: every graph on nnn vertices can have its edge set partitioned…

8 thms2 active usersReviewed
🏆Completed
Algebraic TopologyCombinatoricsGroup Theory·Captain: wurtle

Bounded-degree coboundary expanders in every dimensionResearch Paper

An expander graph is a sparse graph in which every set of vertices has a large edge boundary relative to its size. Expanders with bounded degree are a basic tool across combinatorics, computer science and group theory. High-dimensional expanders are simplicial complexes that extend this behavior to faces of every dimension, and coboundary expansion over …

6 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryProbability·Captain: wurtle

The second Kahn–Kalai conjectureResearch Paper

When does the Erdős–Rényi random graph G(n,p)G(n,p)G(n,p) contain a copy of a prescribed graph HHH? A necessary condition is visible from first moments: if some subgraph F⊆HF\subseteq HF⊆H has expected copy count below a constant, then HHH is unlikely to appear. Kahn and Kalai conjectured in 2007 that this elementary obstruction determines the containment threshold up to a…

47 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: wurtle

A polynomial-time construction of strong thin treesResearch Paper

A thin spanning tree of a graph is a spanning tree that uses only a small fraction of the edges of every cut. Thin trees were introduced for the asymmetric traveling salesman problem: Asadpour, Goemans, Mądry, Oveis Gharan and Saberi showed that a thin tree of low cost can be augmented into a cheap tour, giving an O(log⁡n/log⁡log⁡n)O(\log n/\log\log n)O(logn/loglogn)-approximation (doi:10.1…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: wurtle

The strong thin tree conjectureResearch Paper

A spanning tree keeps a graph connected with as few edges as possible. A spanning tree is thin if, in addition, it uses only a small fraction of the edges of every cut. Thin trees were introduced as a tool for the asymmetric traveling salesman problem (ATSP): Asadpour, Goemans, Mądry, Oveis Gharan and Saberi showed that thin trees, together with cost…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryProbability·Captain: wurtle

Sharp logarithmic exponents for fixed off-diagonal Ramsey numbersResearch Paper

For integers s,t≥2s,t\ge2s,t≥2 the Ramsey number r(s,t)r(s,t)r(s,t) is the least NNN such that every simple graph on NNN vertices contains a clique of order sss or an independent set of order ttt. Ramsey's theorem guarantees these numbers are finite. In the off-diagonal regime, sss is fixed and t→∞t\to\inftyt→∞; the classical upper bounds give r(s,t)=Os ⁣(ts−1/(log⁡t)s−2)r(s,t)=O_s\!\left(t^{s-1}/(\log t)^{s-2}\right)r(s,t)=Os​(ts−1/(logt)s−2),…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryProbability·Captain: wurtle

The sharp logarithmic exponent of r(5,t)Research Paper

For integers s,t≥2s,t\ge 2s,t≥2 the Ramsey number r(s,t)r(s,t)r(s,t) is the least nnn such that every simple graph on nnn vertices contains either a complete subgraph KsK_sKs​ or an independent set of ttt vertices. Determining how r(s,t)r(s,t)r(s,t) grows when sss is fixed and t→∞t\to\inftyt→∞ is one of the central problems of extremal and probabilistic combinatorics: upper bounds come from counting and local…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryRepresentation Theory·Captain: wurtle

Elementary positivity of chromatic quasisymmetric functionsResearch Paper

The chromatic symmetric function of a graph, introduced by Stanley, records all proper colorings of the graph with infinitely many colors as a symmetric function; it refines the chromatic polynomial. Whether it expands with nonnegative coefficients in the basis of elementary symmetric functions ("eee-positivity") is a central question in algebraic…

3 thms2 active usersReviewed
🏆Completed
AlgebraCombinatoricsRepresentation Theory·Captain: wurtle

Combinatorial invariance of Kazhdan–Lusztig polynomialsResearch Paper

Kazhdan–Lusztig polynomials Pu,b(q)P_{u,b}(q)Pu,b​(q) are integer polynomials attached to pairs u≤bu\le bu≤b of elements of a Coxeter group. They were introduced through the canonical basis of the Hecke algebra (Kazhdan–Lusztig, 1979). For Weyl groups they compute local intersection cohomology of Schubert varieties, and they enter the Kazhdan–Lusztig conjectures on characters…

15 thms2 active usersReviewed
🏆Completed
CombinatoricsDiscrete Geometry·Captain: wurtle

A power saving for planar unit distancesResearch Paper

The unit-distance problem of Erdős asks how many pairs among nnn points in the plane can be at distance exactly one. By rescaling, this is the same as asking how often a single distance can repeat. It is one of the central extremal questions of combinatorial geometry and a benchmark for incidence methods. The bound u(n)=O(n4/3)u(n)=O(n^{4/3})u(n)=O(n4/3) of Spencer, Szemerédi and…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsDiscrete Geometry·Captain: wurtle

The weak pinned planar distance theoremResearch Paper

Erdős's distinct-distance problems ask how few different distances nnn points in the plane can determine. The global version, which counts all distances between all pairs, was essentially settled by Guth and Katz, who proved that every nnn-point planar set determines at least cn/log⁡ncn/\log ncn/logn distinct distances (Annals 2015), matching the square lattice up to a …

7 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: wurtle

Balanced counterexamples to Ryser's conjecture at prime ordersResearch Paper

A vertex cover of a hypergraph is a set of vertices meeting every edge; the covering number τ(H)\tau(H)τ(H) is the minimum size of a cover, and the matching number ν(H)\nu(H)ν(H) is the maximum number of pairwise disjoint edges. An rrr-partite rrr-uniform hypergraph has rrr disjoint vertex parts, and every edge takes exactly one vertex from each part. Ryser's covering conjecture…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsNumber Theory·Captain: wurtle

Quantitative Superexponential Bounds for van der Waerden NumbersResearch Paper

Van der Waerden's theorem (1927) says that for every number of colours rrr and every length kkk, every rrr-colouring of a long enough interval of integers contains a monochromatic arithmetic progression of length kkk. The van der Waerden number Wr(k)W_r(k)Wr​(k) is the least such interval length. Its upper bounds were for a long time not even primitive recursive (Shelah 1988…

2 thms2 active usersReviewed
🏆Completed
Algebraic TopologyCombinatoricsDiscrete Geometry·Captain: wurtle

A nine-dimensional counterexample to Borsuk's covering assertionResearch Paper

In 1933 Borsuk asked whether every bounded set of positive diameter in Rd\mathbb R^dRd can be split into d+1d+1d+1 pieces of strictly smaller diameter. The answer is yes in dimensions d≤3d\le3d≤3 and for smooth convex bodies, and a regular simplex shows that d+1d+1d+1 pieces may be necessary. Kahn and Kalai showed in 1993 that the answer is no in high dimensions, and since then…

8 thms2 active usersReviewed
🏆Completed
Dynamical SystemsPure Mathematics·Captain: wurtle

Ergodicity of triangular billiards with an irrational angleResearch Paper

A billiard in a polygon is a point moving at unit speed inside the table and reflecting off the sides by the law "angle of incidence equals angle of reflection". It is one of the simplest Hamiltonian systems and a standard model in mathematical physics; triangles also model two point masses colliding on a segment. The natural invariant probability measure…

2 thms2 active usersReviewed
🏆Completed
AnalysisDynamical Systems·Captain: wurtle

Boundedness and persistence of weakly reversible mass-action systemsResearch Paper

Chemical reaction network theory studies the polynomial differential equations that describe concentrations of interacting species under mass-action kinetics, where each reaction proceeds at a rate proportional to the product of the concentrations of its reactants. A central theme is which properties of the dynamics are forced by the structure of the…

2 thms2 active usersReviewed
🏆Completed
Dynamical SystemsProbability·Captain: wurtle

Rokhlin's multiple-mixing problem for one transformationResearch Paper

Mixing is the basic notion of asymptotic independence in ergodic theory: a measure-preserving transformation TTT is mixing if the event AAA at time 000 and the event BBB at time nnn become independent as n→∞n\to\inftyn→∞. Mixing of order kkk asks the same for kkk events at times whose gaps all tend to infinity. In 1949 Rokhlin introduced higher-order mixing and asked whether…

6 thms2 active usersReviewed
🏆Completed
Dynamical SystemsFunctional AnalysisHarmonic Analysis·Captain: wurtle

A smooth three-torus diffeomorphism with simple Lebesgue spectrumResearch Paper

A measure-preserving transformation TTT of a probability space acts on square-integrable functions by the Koopman operator UTg=g∘TU_Tg=g\circ TUT​g=g∘T, a unitary operator. Its spectral type (discrete, singular continuous, absolutely continuous) and its multiplicity are basic invariants of ergodic theory. The Lebesgue spectrum is the spectral type of the shift on …

4 thms2 active usersReviewed
🏆Completed
AnalysisDynamical Systems·Captain: wurtle

Two limit cycles for quintic Liénard systemsResearch Paper

A limit cycle of a planar vector field is a periodic orbit that is isolated among periodic orbits. The second part of Hilbert's sixteenth problem asks how many limit cycles a polynomial vector field of a given degree can have, and it is open even for quadratic fields. The classical Liénard systems

9 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityTheoretical Computer Science·Captain: wurtle

Subsphere methods for memory-sample lower bounds in noiseless Gaussian regressionResearch Paper

An exact linear equation can carry arbitrarily fine real information: ddd independent Gaussian equations Yt=⟨Xt,s⟩Y_t = \langle X_t, s\rangleYt​=⟨Xt​,s⟩ determine a vector s∈Rds \in \mathbb{R}^ds∈Rd almost surely. A streaming learner that keeps only finitely many persistent states cannot retain those equations at arbitrary precision. The question is how many fresh equations such a…

45 thms2 active usersReviewed
🏆Completed
Information TheoryProbabilityTheoretical Computer Science·Captain: wurtle

Replacing Gaussian observations in memory-constrained inferenceResearch Paper

A finite message chosen from data changes the conditional distribution of those data. In memory-constrained inference this matters directly: a learner observing a signal SSS through exact Gaussian equations keeps a finite state WWW, and after conditioning on WWW the rows that were used to select it are biased. An independent Gaussian matrix has the same…

16 thms2 active usersReviewed
🏆Completed
Information TheoryProbabilityTheoretical Computer Science·Captain: wurtle

Localization costs and information growth for exact Gaussian observationsResearch Paper

An exact linear observation ⟨x,S⟩\langle x, S\rangle⟨x,S⟩ of a real signal can carry arbitrarily many bits. A finite message computed from a block of such observations cannot, but its information content is not controlled by the number of observations alone: if earlier messages have already concentrated the signal in a small region, the next block can exploit that…

5 thms2 active usersReviewed
PreviousPage 10 of 13Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1DBdbenbenn24962643
2EYEyal199010981568
3SCShuze Chen8223255
4FIfizzyinc34100
5MAmarwahaha5672
6POpolylog448
7WUwurtle35882
8ECEthan Cheung Wang2815
9WIWillR202
10YXYuxuan Xu1834

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me