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

A counterexample to Ryser's covering conjecture

There exists s0s_0 such that, for every prime s≥s0s \ge s_0 with s≡2(mod3)s \equiv 2 \pmod{3}, there is an integer n0(s)≥3n_0(s) \ge 3 such that for every odd integer n≥n0(s)n \ge n_0(s) and q=snq = s^n, there is a finite intersecting (q+1)(q+1)-partite (q+1)(q+1)-uniform hypergraph HH satisfying τ(H)=q+1\tau(H) = q+1, disproving the intersecting case of Ryser's covering conjecture.

For every prime s≥s0s \ge s_0 with s≡2(mod3)s \equiv 2 \pmod{3} and every odd integer n≥n0(s)n \ge n_0(s), putting r=sn+1r = s^n + 1, there is a finite simple complete graph with an rr-edge-coloring for which the minimum number of monochromatic trees (or connected monochromatic subgraphs, or maximal monochromatic components) needed to cover its vertices is exactly rr.

There exist absolute constants κ∈(0,1/10)\kappa \in (0, 1/10) and QQ such that if q≥Qq \ge Q is a prime power and every proper subfield of Fq\mathbb{F}_q has order at most q1/3q^{1/3}, then any sets PP of projective points and L\mathcal{L} of projective lines over Fq\mathbb{F}_q with ∣P∣,∣L∣≤q1+κ|P|, |\mathcal{L}| \le q^{1+\kappa} satisfy I(P,L)≤q3/2−κI(P, \mathcal{L}) \le q^{3/2-\kappa}.

Under the random deletion hypotheses of Lemma 3.2 as q→∞q \to \infty through prime powers whose proper subfields have order at most q1/3q^{1/3}, with probability tending to one, every affine line ℓ\ell has ∣Xℓ∩ℓ∣≥δq/2|X^\ell \cap \ell| \ge \delta q/2, and every set of at most qq affine lines covering all but at most 2q2q points of XX contains at least (1−ρ)q(1-\rho)q lines through a common projective point.

For every positive integer DD there is K=K(D)K = K(D) such that, as q→∞q \to \infty through prime powers, given n≤Dqn \le Dq configurations Wi⊆Fq2W_i \subseteq \mathbb{F}_q^2 and direction sets DiD_i with ∣Wi∣,∣Di∣≤D|W_i|, |D_i| \le D and each direction in at most DD sets DiD_i, drawing KK independent uniform shifts per group yields a conflict-free selection of one translate per group with probability tending to one.

For every sufficiently large prime s≡2(mod3)s \equiv 2 \pmod{3}, there is a set Y⊆Fs2Y \subseteq \mathbb{F}_s^2 obtained by deleting one affine line ℓd\ell_d of each slope d∈Fs∗d \in \mathbb{F}_s^* such that every other line of slope d∈Fs∗d \in \mathbb{F}_s^* contains at least five points of YY, f(x,y)=(x3,y)f(x,y) = (x^3,y) is a bijection, every affine line contains at least s/8s/8 points of f(Y)f(Y), and any cover of f(Y)f(Y) by aa affine lines and bb individual points with a+b/2≤sa + b/2 \le s satisfies a=sa = s, b=0b = 0, and the lines form a full parallel class.

Methods

Uniform incidence saving over finite fields with bounded proper subfields using incidence graph pruning, four-anchor projective-coordinate reduction, simultaneous difference-quotient extraction, and uniform scalar coverings.

Source excerpts

“The proof follows the incidence and sum–product strategy of Bourgain, Katz, and Tao [9, Sections 3–4 and 6]. Its geometric step turns an incidence configuration with too many incidences into a dense set of pairs whose differences and quotients range over small sets. A graph argument then extracts one subset with both a small difference set and a small quotient set. Finally, scalar coverings show that such a subset cannot have size near the square root of the field order under the proper-subfield hypothesis.” · Show in paper

Martingale concentration and random-deletion line-cover analysis to force any small line cover of surviving points to contain almost a full pencil.

Source excerpts

“The purpose of this section is to show that a set of at most q lines covering almost all survivors of a suitable random deletion process must contain almost a full pencil. The deletions within a single trial may be dependent; independence is required only between trials.” · Show in paper

Independent-transversal domination-certificate method for selecting conflict-free translates from independent random pools.

Source excerpts

“To prove the theorem, make each candidate a vertex of a graph and join candidates from different pools when they conflict. We seek an independent set containing one vertex from each pool, called an independent transversal. Its nonexistence has a small domination certificate.” · Show in paper

Dual-coordinatization construction in a prime plane using the cubing bijection f(x, y) = (x^3, y) to combine line-survival in original coordinates with cover rigidity in transformed coordinates.

Source excerpts

“In the original coordinates we delete one line in every finite nonzero direction. After the change of coordinates, the deleted sets become curves, so the line-survival conclusion of Lemma 3.2 applies to every line. It will force every small mixed cover by lines and individual points to be a parallel class.” · Show in paper

Ambient placement of linearly transformed copies of a small-field configuration in an odd-degree extension field plane, modifying line labels in assigned directions to preserve intersection while ruling out small covers.

Source excerpts

“We will place copies of Y in a larger affine plane, assign each copy the directions in which its labels will change, and delete the ambient lines of those directions that meet it.” · Show in paper