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

Balanced counterexamples to Ryser's conjecture at prime orders

There exists q0q_0 such that, for every prime q≥q0q \ge q_0, there is a finite intersecting (q+1)(q+1)-partite (q+1)(q+1)-uniform hypergraph HH with ∣V1∣=⋯=∣Vq+1∣=q+1|V_1| = \cdots = |V_{q+1}| = q + 1, τ(H)=q+1\tau(H) = q + 1, and every vertex belonging to an edge, which disproves Ryser's covering conjecture even for intersecting hypergraphs with equally sized parts.

For every sufficiently large prime qq, there is a finite complete graph with a (q+1)(q+1)-edge-coloring whose vertices require exactly q+1q+1 monochromatic trees (or connected monochromatic subgraphs) to cover.

Let q≥4q \ge 4 be a prime power. If a compatible collection of valid tuples in Fq2\mathbb{F}_q^2 satisfies occupancy, concentration of core covers, and the local condition with parameters 0<ρ<10 < \rho < 1 and B≥0B \ge 0 satisfying ρq>2(1+B)\rho q > 2(1+B), then there is an intersecting (q+1)(q+1)-partite (q+1)(q+1)-uniform hypergraph with exactly q+1q+1 nonisolated vertices in each part and cover number q+1q+1, with edges in bijection with XX.

For fixed k≥1k \ge 1 and K≥0K \ge 0, if QqQ_q is a probability law on sets D⊆LD \subseteq \mathcal{L} with kk lines per direction satisfying Qq(D)≤eKqUq,k(D)Q_q(D) \le e^{Kq} U_{q,k}(D) for every DD, then as q→∞q \to \infty through prime powers: (i) the empirical multiplicity measure converges in probability in total variation to Poisson(k)\mathrm{Poisson}(k); (ii) for μ=e−k\mu = e^{-k} and fixed λ,η>0\lambda, \eta > 0, the probability that at least ηq\eta q lines ℓ∈L∖D\ell \in \mathcal{L} \setminus D deviate from μq\mu q by at least λq\lambda q tends to zero; (iii) for fixed δ>0\delta > 0, the probability that there is C⊆L∖DC \subseteq \mathcal{L} \setminus D with ∣C∣≤q|C| \le q covering RDR_D and leaving at least δq2\delta q^2 points of AA uncovered tends to zero.

Under the laws of Theorem 3.1, as q→∞q \to \infty through primes, for each fixed ζ>0\zeta > 0, with probability tending to one, every set C⊆L∖DC \subseteq \mathcal{L} \setminus D of at most qq lines covering RDR_D has at least (1−ζ)q(1-\zeta)q members through a common projective point.

In the independent uniform sampling model for Mg0,Mg1∈LgM_g^0, M_g^1 \in \mathcal{L}_g, there are constants c∗>0c_* > 0 and C∗<∞C_* < \infty such that with probability 1−o(1)1 - o(1) (and jointly with Mg0≠Mg1M_g^0 \ne M_g^1 for all gg with probability e−1+o(1)e^{-1} + o(1)), the candidate graph of retained valid tuples satisfies ∣Qg∣∈[c∗q,q]|Q_g| \in [c_* q, q], maximum degree ≤C∗q\le C_* q, within-slot degree ≤q1/8\le q^{1/8}, codegree ≤q1/8\le q^{1/8} outside an exceptional set J(v)J(v) of size ≤q1/8\le q^{1/8}, constituent multiplicity ≤⌈log⁡q⌉\le \lceil \log q \rceil, and at least q/5q/5 uncovered points on every line other than Mg1M_g^1.

For sufficiently large qq and a graph partitioned into n=2(q+1)n = 2(q+1) slots QiQ_i satisfying the degree, within-slot degree, and codegree bounds (21)–(22) with β=1/8\beta = 1/8, there exist constants K∗,ρ>0K_*, \rho > 0 and a random procedure returning an independent transversal with probability 1−o(1)1 - o(1), such that any cylinder prescribing choices in ss distinct slots jointly with success has probability at most (K∗/q)s(K_*/q)^s, and any fixed sets Tℓ⊆ℓT_\ell \subseteq \ell of size ≥c0q\ge c_0 q retain at least ρq\rho q points on every line ℓ\ell with probability 1−o(1)1 - o(1).

Conditional on the selection procedure returning a collection A\mathcal{A}, the law of the deletion set DD (consisting of the selected split lines and the lines Mg1M_g^1) is dominated pointwise by exp⁡(O(q))\exp(O(q)) times the uniform law on sets containing three distinct lines in each direction.

In the independent offset experiment with the selection procedure, the probability that the procedure returns a compatible collection and the local condition fails at some p∈Ap \in A is o(1)o(1).

Methods

Merge-and-split modification of affine-plane line partitions: in each direction gg, merge two parallel lines Mg0,Mg1M_g^0, M_g^1 into one block and split two other parallel lines Sg1,Sg2S_g^1, S_g^2 into opposite-pair blocks {u0,u2}\{u_0, u_2\} and {u1,u3}\{u_1, u_3\} whose consecutive pairs lie in merged blocks of four distinct generator directions.

Source excerpts

“In a given direction, merge two parallel lines into one block, and split two other parallel lines into two blocks each. The count becomes (q − 4) + 1 + 4 = q + 1. Each split line keeps just four designated points. Writing them in a cyclic order as u0, u1, u2, u3, its blocks are the opposite pairs {u0, u2} and {u1, u3}.” · Show in paper

Profile detection and counting lemma: compactify point-multiplicity profiles and use an interleaved exposure test with irrational exponent γ=2\gamma = \sqrt{2} to distinguish (i,j)(i,j) coordinates and obtain exp⁡(−Ω(qlog⁡q))\exp(-\Omega(q \log q)) bounds under Uq,kU_{q,k} that survive an exp⁡(Kq)\exp(Kq) change of measure.

Source excerpts

“Order D and C independently and uniformly, and set nD = k(q + 1) and γ = √2. With equal exposure rates, limiting point-survival probabilities would depend only on i + j. The irrational exponent makes i + γj distinct for distinct pairs (i, j), allowing the exposure test to distinguish both coordinates.” · Show in paper

Prime-plane stability for affine line covers: dualize an affine line cover missing O(q2)O(q^2) points and apply the Szőnyi–Weiner stability theorem in PG(2,q)\mathrm{PG}(2,q) for prime qq to force almost all lines into a common projective pencil.

Source excerpts

“The external geometric input is the stability theorem of Szőnyi and Weiner [19, Theorem 4], also reproduced by Héger and Nagy [12, Result 3.6].” · Show in paper

Two-stage random independent transversal selection with cylinder probability bounds: iteratively select random slots and vertices with thinning to equalize one-step survival probabilities, track stopped/censored Azuma–Hoeffding martingales, and complete the last h0h_0 slots using the Lovász local lemma.

Source excerpts

“The selection has two stages. In the main stage we repeatedly choose a slot and a vertex, delete conflicts, and thin the remaining choices so that every vertex has the same survival probability. Domain sizes then decrease at a common rate. Remaining degrees decrease faster, because the chosen slot also disappears. We show that this difference leaves a sparse enough graph to complete the last slots by the local lemma.” · Show in paper

Acyclic dependency extraction for local cover incidences: given an admissible bad cover at an affine point pp, extract 3−κ3 - \kappa surplus incidence conditions whose underlying anchor dependencies form an acyclic directed graph, allowing successive integration of independent uniform variables.

Source excerpts

“The surplus count alone does not allow us to multiply incidence probabilities: one condition may depend on another condition’s variable. We therefore extract a collection with acyclic dependencies.” · Show in paper