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 Sidorenko's conjecture

Let HH be the incidence graph of the 22 triples on 13 points in Table 1, which is a bipartite graph with 35 vertices and 66 edges. There is a finite simple undirected graph GG with at least one edge such that t(H,G)<p(G)66t(H, G) < p(G)^{66}, disproving Sidorenko's conjecture.

For the same graph HH as in Theorem 1.1: (i) for every c>0c > 0, there is a finite simple undirected graph FF with p(F)>0p(F) > 0 such that t(H,F)<c p(F)66t(H, F) < c\, p(F)^{66}; and (ii) there are p∗∈(0,1)p_* \in (0, 1), δ∗>0\delta_* > 0, and finite simple undirected graphs FsF_s of orders ns→∞n_s \to \infty for which ds=∣E(Fs)∣/(ns2)→p∗d_s = |E(F_s)|/\binom{n_s}{2} \to p_* and Inj(H,Fs)≤(1−δ∗)(ns)35ds66\mathrm{Inj}(H, F_s) \le (1 - \delta_*)(n_s)_{35} d_s^{66} for all sufficiently large ss.

For the same connected bipartite graph HH of Theorem 1.1, there are p∈(0,1)p \in (0, 1) and a nonconstant graphon WW such that t(K2,W)=pt(K_2, W) = p and t(H,W)=p66t(H, W) = p^{66}. Consequently, HH is not pp-forcing at this density and hence is not forcing, despite being bipartite and containing a cycle.

The complex of 22 triples on 13 points in Table 1 satisfies: (1) every pair in EE lies in exactly two faces, ∣E∣=33|E| = 33, and the face-neighbor graph is connected; (2) for each bit position, each of its two classes consists of 11 faces covering all 13 points with an exposure ordering; (3) every ae≥1/3a_e \ge 1/3 and some ae>1/3a_e > 1/3; and (4) color refinement of HH, starting with a separate color for each part, eventually gives distinct colors to all vertices within either part.

There is an integer D0D_0 such that for every fixed even D≥D0D \ge D_0, as q→∞q \to \infty through odd primes, for independent uniform Xi,Yj∈SDX_i, Y_j \in \mathcal{S}_D, every B⊆CB \subseteq \mathcal{C}, and every choice of signs ξij∈{1,−1}\xi_{ij} \in \{1, -1\} on BB, E∏(i,j)∈BKξij(Xi−Yj)=Eη∏j∈J∏e={i,k}⊂j,(i,j),(k,j)∈B(1+c0ηeξijξkj)+o(1)\mathbb{E}\prod_{(i,j)\in B} K_{\xi_{ij}}(X_i - Y_j) = \mathbb{E}_\eta \prod_{j\in J} \prod_{e=\{i,k\}\subset j, (i,j),(k,j)\in B} (1 + c_0 \eta_e \xi_{ij} \xi_{kj}) + o(1) uniformly over BB and sign choices (and similarly for Yj−XiY_j - X_i).

Assuming Lemma 3.1, there is a symmetric kernel U:Ω×Ω→[0,1]U : \Omega \times \Omega \to [0, 1] on a finite probability space with mean μ>0\mu > 0 such that t(H,U)<μ66t(H, U) < \mu^{66}.

If UU is a symmetric [0,1][0, 1]-valued kernel on a finite probability space with μ=EU>0\mu = \mathbb{E}U > 0, τ=t(H,U)\tau = t(H, U), and Δ=μ66−τ>0\Delta = \mu^{66} - \tau > 0, then for any integer n>(595+66μ66)/Δn > (595 + 66\mu^{66})/\Delta, there is a finite simple graph GG on nn vertices with t(H,G)<p(G)66t(H, G) < p(G)^{66}.

For every fixed even D≥12D \ge 12, every activity pattern B⊆CB \subseteq \mathcal{C}, and every prescribed set of incidence signs, E[1T∏(i,j)∈BKξij(Xi−Yj)]=Eη∏j∈J∏{i,k}⊆Aj(1+c0η{i,k}ξijξkj)+o(1)\mathbb{E}[\mathbf{1}_{\mathcal{T}} \prod_{(i,j)\in B} K_{\xi_{ij}}(X_i - Y_j)] = \mathbb{E}_\eta \prod_{j\in J} \prod_{\{i,k\}\subseteq A_j} (1 + c_0 \eta_{\{i,k\}} \xi_{ij} \xi_{kj}) + o(1) uniformly.

For every sufficiently large even D=2rD = 2r and every activity set B⊆CB \subseteq \mathcal{C}, EL,Y[1{∃e={i,k}∈E:dim⁡(Li∩Lk)>0}∏(i,j)∈BJ(Li,Yj)]=o(1)\mathbb{E}_{L,Y}[\mathbf{1}_{\{\exists e=\{i,k\}\in E : \dim(L_i \cap L_k) > 0\}} \prod_{(i,j)\in B} J(L_i, Y_j)] = o(1) as q→∞q \to \infty through odd primes, with DD fixed.

Methods

Rank-layer symmetric matrix kernel over F_q with even dimension D = 2r, independent matrix coordinates per incidence, and activation laws with zero nonconstant first sign moments and signed overlap moments.

Source excerpts

“Fix a positive even dimension D = 2r and set K_xi(Z) = 1_{rank Z = r, sign(Z) = xi} / PZ′inSDP_{Z' in S_D}(rank Z' = r, sign(Z') = xi), xi in {1, -1}, c_0 = chi((-1)^r).” · Show in paper

“Define W_q((a, x), (b, y)) = ES,xi∣a,bE_{S, xi | a, b} prod_{kappa in S} KxikappaK_{xi_kappa}(x^kappa - y^kappa).” · Show in paper

Color-refinement vertex and pair scoring to make the identity type assignment the unique maximizer over all part-preserving type maps, including noninjective maps.

Source excerpts

“There are real vertex scores s_t, t in P sqcup Q, and pair scores sabs_{ab}, (a, b) in P x Q, such that the identity is the unique maximizer of Q(f) = sum_{u in P sqcup Q} sf(u)s_{f(u)} + sum_{{u,v} in L, u in P} sf(u)f(v)s_{f(u)f(v)} over all maps f preserving the two parts.” · Show in paper

Inactive-type dilution and crossed-product symmetrization to convert a negative limiting coefficient in one orientation into a symmetric [0,1]-valued kernel with a strict H-density deficit.

Source excerpts

“Add an inactive type * to A = I, giving it probability 1 - epsilon and giving each old type a probability epsilon * pi_a, where 0 < epsilon < 1. Every pair involving * uses S = emptyset.” · Show in paper

“Define V((x, y), (x', y')) = W(x, y') W(x', y). ... Let L = max V, which is finite and at least one, and set U = V / L.” · Show in paper

Symplectic Lagrangian subspace reduction and planted-law density ratio to bound singular point-difference contributions in the rank-layer model.

Source excerpts

“For X in S_D, write Gamma_X = {(x, Xx) : x in F_q^D}, where coordinates identify a symmetric matrix with a map to the dual. ... dim(Gamma_X cap Gamma_Y) = D - rank(X - Y).” · Show in paper

“Define the planted law nu by first choosing Y uniformly and then, conditional on Y, choosing the three L_i independently and uniformly subject to dim(L_i cap Y) = r.” · Show in paper

Categorical tensor powers, balanced independent blow-ups, and convex kernel interpolation with independent random-graph sampling to derive amplification, injective supersaturation, and forcing-conjecture failure.

Source excerpts

“Let GtimesrG^{times r} be the categorical power, whose adjacency is coordinatewise. ... For (ii), use instead the balanced independent blow-ups F_s = G[s]” · Show in paper

“Lift the two kernels to the independent coordinates of Omega = V(G) x {-1, 1}, with product probability, and set W_s((x, a), (y, b)) = (1 - s) W_0(x, y) + s W_1(a, b), 0 <= s <= 1.” · Show in paper