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 crossing number of complete bipartite graphs

For all positive integers m,nm, n, the ordinary crossing number of the complete bipartite graph Km,nK_{m,n} is cr⁡(Km,n)=dmdn=⌊m/2⌋⌊(m−1)/2⌋⌊n/2⌋⌊(n−1)/2⌋\operatorname{cr}(K_{m,n}) = d_m d_n = \lfloor m/2 \rfloor \lfloor (m-1)/2 \rfloor \lfloor n/2 \rfloor \lfloor (n-1)/2 \rfloor.

Let WW be a real vector space of dimension NN, and let U1,…,Um,V1,…,VmU_1, \dots, U_m, V_1, \dots, V_m be subspaces of WW (m≥1m \ge 1) such that Ui∩Vi={0}U_i \cap V_i = \{0\} for every ii. Then ∑i,j=1mdim⁡(Ui∩Vj)≤⌊m2/4⌋N\sum_{i,j=1}^m \dim(U_i \cap V_j) \le \lfloor m^2/4 \rfloor N, and this constant is sharp.

Let X1,…,Xm,Y1,…,YmX_1, \dots, X_m, Y_1, \dots, Y_m be real d×dd \times d matrices such that Xi−YiX_i - Y_i is invertible for every ii. Then ∑1≤i,j≤m, i≠jrank⁡(Xi−Yj)≥2dmd\sum_{1 \le i,j \le m,\, i \neq j} \operatorname{rank}(X_i - Y_j) \ge 2 d_m d, where dm=⌊m/2⌋⌊(m−1)/2⌋d_m = \lfloor m/2 \rfloor \lfloor (m-1)/2 \rfloor.

In a normalized minimum drawing of Km,nK_{m,n}, if z,y∈RE(Km,n)z, y \in \mathbb{R}^{E(K_{m,n})} are the signed edge vectors of two oriented simple graph cycles (which may share vertices and edges, and traverse shared edges in opposite directions), then zTJy=0z^{\mathsf{T}} J y = 0.

For every 1≤i,k≤m1 \le i, k \le m, the signed-intersection blocks satisfy Jik−Ji1−J1k+J11∈LJ^{ik} - J^{i1} - J^{1k} + J^{11} \in \mathcal{L}, where L={H∈Rn×n:H(p,q)=rp+cq for some r,c∈Rn}\mathcal{L} = \{H \in \mathbb{R}^{n \times n} : H(p, q) = r_p + c_q \text{ for some } r, c \in \mathbb{R}^n\}.

For any pairwise distinct real numbers x1,…,x2s+1x_1, \dots, x_{2s+1}, the values at (xp,xq)(x_p, x_q) for (p,q)∈Qs={(p,q):1≤q<p≤s+1}∪{(p,q):s+1<p<q≤2s+1}(p, q) \in Q_s = \{(p, q) : 1 \le q < p \le s+1\} \cup \{(p, q) : s+1 < p < q \le 2s+1\} uniquely determine a polynomial of degree at most s−1s-1 in each variable.

For n=2s+1n = 2s + 1, d=s2d = s^2, and any pairwise distinct real numbers x1,…,xnx_1, \dots, x_n, there is a linear map Φ:Rn×n→Rd×d\Phi : \mathbb{R}^{n \times n} \to \mathbb{R}^{d \times d} that annihilates every additive matrix H(p,q)=rp+cqH(p, q) = r_p + c_q and every diagonal matrix, sends each coordinate matrix EpqE_{pq} (p≠qp \neq q) to a rank-one matrix, and sends S≺S_\prec to an invertible matrix for every strict linear order ≺\prec on {1,…,n}\{1, \dots, n\} simultaneously.

An admissible continuous-arc drawing of a finite simple graph can be replaced by a polygonal drawing with no more crossing points, with edges straight near every vertex and crossing, and with no crossings between edges sharing an endpoint.

Methods

Polynomial evaluation filtration and determinant multiplicity method for bounding sums of subspace intersection dimensions under diagonal disjointness.

Source excerpts

“We encode the subspaces by polynomial evaluation constraints. Evaluating away from the constraint nodes gives a filtration of evaluation spaces. At each node, disjointness bounds the evaluated rank. The resulting rank deficiency gives a lower bound on a polynomial minor's vanishing order.” · Show in paper

Signed-intersection and half-order cycle pairing using left and right parallel shifts of polygonal walks and a coning argument to relate crossing matrices to cycle intersections.

Source excerpts

“For the second cycle construct two closed polygonal walks eta_+ and eta_- by shifting its edge tracks a small distance to the left and to the right, respectively, relative to the fixed graph-edge orientation.” · Show in paper

Barycentric Lagrange interpolation rank-detector map on square matrices using two-triangle bivariate polynomial interpolation to annihilate additive and diagonal terms while preserving full rank on linear-order sign matrices.

Source excerpts

“The factors 1/F'(x_p) are the classical barycentric weights for Lagrange interpolation [2, Section 3, equation (3.2)].” · Show in paper

Continuous-arc drawing normalization by isolating vertex and crossing disks, replacing exterior arcs with polygonal paths, and iteratively removing adjacent-edge crossings.

Source excerpts

“Isolating the marked passages. Call the vertices and crossing points of the given drawing its marks. There are finitely many. Parameterize each edge injectively by gamma_e : [0, 1] -> R^2.” · Show in paper