By OpenAISourceGitHub

Manuscripts from openai/math

Fork
Clone
git clone https://openversions.com/git/index/openai-math.git
Cite
Version link
https://openversions.com/index/openai-math/commit/dfd8c46870b48511e697cbb43a3c8c91d375fa2f
Version identifier (commit hash)
dfd8c46870b48511e697cbb43a3c8c91d375fa2f

Fork to create your own copy with credit to the source. Clone to get a Git copy on your computer.

All papers

Claims

Findings

The hypercube Ramsey number has linear order

There is an absolute constant C>0C > 0 such that the two-color Ramsey number of the nn-dimensional binary cube satisfies R(Qn)≤C2nR(Q_n) \leq C 2^n for every integer n≥0n \geq 0, resolving positively the hypercube Ramsey conjecture of Burr and Erdős.

If HH is a not necessarily induced subgraph of QdQ_d and 2d≤A∣V(H)∣2^d \leq A|V(H)| for a fixed A≥1A \geq 1, then R(H)≤CA∣V(H)∣R(H) \leq CA|V(H)|; in particular, for integers d≥0d \geq 0 and k≥1k \geq 1 and any spanning subgraph FF of QdQ_d, its Cartesian power satisfies R(F□k)≤C∣V(F)∣kR(F^{\square k}) \leq C|V(F)|^k with the same absolute constant CC for all permitted F,d,kF, d, k.

After passing to a subsequence of a counterexample sequence and discarding o(N)o(N) labels, there is a fixed η0>0\eta_0 > 0 such that for every pair of probability laws μ,ν\mu, \nu on the retained sides and either color GG, width(μ),width(ν)≤nη0  ⟹  ∣dG(μ,ν)−1/2∣≤n−η0\mathrm{width}(\mu), \mathrm{width}(\nu) \leq n^{\eta_0} \implies |d_G(\mu, \nu) - 1/2| \leq n^{-\eta_0}.

Under initial discrepancy (7.2) in both orientations, full-dimensional one-color cluster witnesses with first law and aggregate second law of widths ≤nδ\leq n^\delta, individual cluster atoms ≤exp⁡(−nζ)\leq \exp(-n^\zeta), and within-cluster GG-codegrees ≥1/4+n−δ\geq 1/4 + n^{-\delta} (for δ<min⁡(η0,ζ,1)/2000\delta < \min(\eta_0, \zeta, 1)/2000) yield a monochromatic cube and are eventually absent for every fixed rational admissible parameter choice.

In the stabilized contradiction sequence with full cluster exclusions, neither intermediate sublinear bias (H†<1H^\dagger < 1) nor intermediate linear bias (H†≥1H^\dagger \geq 1 and 0<HL†<10 < H_L^\dagger < 1) nor a linear-budget jump (H†≥1H^\dagger \geq 1 in both orientations and HL†=0H_L^\dagger = 0 in one) can occur; consequently, there are constants 0<x∗<.010 < x_* < .01 and 0<α<.010 < \alpha < .01 for which ∣dG(σ,π)−1/2∣≤n−1+.04|d_G(\sigma, \pi) - 1/2| \leq n^{-1+.04} at widths αn,nx∗\alpha n, n^{x_*} in either order.

In the deep-discrepancy regime, there exist pairwise disjoint patches (Xi,Yi)(X_i, Y_i) with ∣Xi∣=∣Yi∣=Mi|X_i| = |Y_i| = M_i and ∑iMi=S≥cN\sum_i M_i = S \geq cN (c>0c > 0 fixed), all of one mode (bounded, direct bias, or cluster), orientation, and color, admitting a dyadic prefix allocation ∑i2−ℓi=1\sum_i 2^{-\ell_i} = 1 with Mi/S≤2−ℓi<2Mi/SM_i/S \leq 2^{-\ell_i} < 2M_i/S.

Both high modes (high direct and high cluster with small or large bins) and low modes (bounded, low direct, and low cluster) of the tiling yield a monochromatic copy of QnQ_n, contradicting the counterexample sequence.

Methods

Stabilization of countable existence properties to finite menus with o(N)o(N) label removals and balanced mixtures / simultaneous profiles via Kakutani's fixed-point theorem.

Source excerpts

“Lemma 3.2 (Stabilization and finite menus). For a countable list of existence properties defined by witnesses intrinsic to their supports, we can pass to a subsequence and discard o(N) labels so that each property is either eventually absent or available.” · Show in paper

“Lemma 3.3 (Balanced mixtures and simultaneous profiles).” · Show in paper

Conditional avoidance comparison (lopsided Lovász Local Lemma), scattered moments for column-sum control, and gated posterior comparison for dependent random choice.

Source excerpts

“Lemma 3.5 (Conditional avoidance comparison).” · Show in paper

“Lemma 3.6 (Scattered moments).” · Show in paper

“Lemma 3.7 (Gated posterior comparison).” · Show in paper

Geometric height device for local center selection in Hamming balls with bounded level differences and short-radius truncation.

Source excerpts

“Lemma 3.8 (Local height selection).” · Show in paper

Calibrated near-product injections preserving exact individual marginals and clock sampling for injective assignments avoiding local failure predicates.

Source excerpts

“Lemma 3.9 (Calibrated near-product injections).” · Show in paper

“Lemma 3.10 (Clock sampling).” · Show in paper

Heterogeneous centered-moment identity, interaction-tail bounds, and homogeneous clique peeling for common-neighbor mass lower tails.

Source excerpts

“Lemma 12.2 (Heterogeneous centered-moment identity).” · Show in paper

“Lemma 12.5 (Homogeneous extension counts and peeling).” · Show in paper

Parallel Moser–Tardos initial resampling with multiplicative final-state comparison, late syndrome-class exposure, and two-endpoint Hall matching.

Source excerpts

“Proposition 17.4 (Finite resampling and multiplicative comparison).” · Show in paper

“Lemma 18.6 (Two-endpoint Hall estimate).” · Show in paper