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 logarithmic independence bound for clique-free graphs

For every integer r≥4r \ge 4, there is a constant cr>0c_r > 0 depending only on rr such that every finite simple KrK_r-free graph GG with nn vertices and average degree d≥2d \ge 2 satisfies α(G)≥crnlog⁡dd\alpha(G) \ge c_r \frac{n \log d}{d}.

For every integer r≥2r \ge 2, if ww maximizes FGF_G on a nonempty finite KrK_r-free graph GG, then for every x≥1x \ge 1 and all vertex sets S,D⊆V(G)S, D \subseteq V(G) with w(S),w(D)≤exw(S), w(D) \le e^x, the directed cross mass satisfies ew(S,D)≤Crgx(w(S))e_w(S, D) \le C_r g_x(w(S)) with Cr=16r2C_r = 16 r^2.

Let r≥2r \ge 2 be an integer, GG be a finite KrK_r-free graph with positive vertex weights ww, and s=w(V(G))s = w(V(G)). For every 0<ε≤1/20 < \varepsilon \le 1/2, there exist jointly distributed random variables (mv)v∈V(G)(m_v)_{v \in V(G)} with finite support such that 0≤mv≤br(ε):=2r(r−2)ε−(r−2)0 \le m_v \le b_r(\varepsilon) := 2^{r(r-2)} \varepsilon^{-(r-2)}, Emv=1\mathbb{E} m_v = 1, and EMG((wvmv)v)≤εs2\mathbb{E} M_G((w_v m_v)_v) \le \varepsilon s^2.

For every C≥1C \ge 1, there is a constant C△(C)C_\triangle(C) such that if GG is a finite simple graph with positive vertex weights ww satisfying the cross-mass bound (3.1) with constant CC, then TG(w)≤C△(C)MG(w)T_G(w) \le C_\triangle(C) M_G(w).

Under the cross-mass condition (3.1) with constant C≥1C \ge 1 and neighborhood/common-neighbor bounds (4.1) for x≥32x \ge 32, each kernel KujK_u^j is reversible with stationary measure πu\pi_u and satisfies Kuj(v,y)≤xwyK_u^j(v, y) \le x w_y, −log⁡x≤H0≤⋯≤HR≤AClog⁡x-\log x \le H_0 \le \dots \le H_R \le A_C \log x for R=⌈x⌉R = \lceil x \rceil, and there exists j∈{0,…,R−1}j \in \{0, \dots, R-1\} such that under the ordered triangle law E∥Kuj(v,⋅)−Kuj(z,⋅)∥TV≤BClog⁡xx\mathbb{E}\|K_u^j(v, \cdot) - K_u^j(z, \cdot)\|_{\mathrm{TV}} \le B_C \sqrt{\frac{\log x}{x}}.

Let GG be a finite positive-vertex-weighted graph satisfying the cross-mass condition (3.1) with constant C≥1C \ge 1, and suppose max⁡vw(NG(v))≤ex\max_v w(N_G(v)) \le e^x for some x>X(C)x > X(C). Then there is a finite positive-vertex-weighted graph G′G' with a weight-preserving map to GG injective on directed edges such that max⁡vw(NG′(v))≤ex\max_v w(N_{G'}(v)) \le e^{\sqrt{x}}, TG′(w)≥(1−aClog⁡xx)TG(w)−MG(w)xT_{G'}(w) \ge (1 - a_C \frac{\log x}{\sqrt{x}}) T_G(w) - \frac{M_G(w)}{x}, MG′(w)≤MG(w)M_{G'}(w) \le M_G(w), and G′G' satisfies (3.1) with constant CC.

For every integer r≥4r \ge 4, every real number Δ≥3\Delta \ge 3, and every finite KrK_r-free graph GG with nn vertices and maximum degree at most Δ\Delta, α(G)≥FG∗Drlog⁡Δ\alpha(G) \ge \frac{F_G^*}{D_r \log \Delta} and α(G)≥nlog⁡Δ4DrΔ\alpha(G) \ge \frac{n \log \Delta}{4 D_r \Delta}.

Methods

Entropy-minus-edge potential FG(w)=∑v∈V(G)wv(1−log⁡wv)−MG(w)F_G(w) = \sum_{v \in V(G)} w_v (1 - \log w_v) - M_G(w) maximized over nonnegative vertex weights ww.

Source excerpts

“FG(w) = sum_{v in V(G)} wv(1 - log wv) - MG(w), F*_G = max_{w >= 0} FG(w).” · Show in paper

Recursive random multipliers mvm_v on KrK_r-free graphs that preserve vertex weights in expectation (Emv=1\mathbb{E} m_v = 1) while keeping expected edge mass small (EMG((wvmv)v)≤εs2\mathbb{E} M_G((w_v m_v)_v) \le \varepsilon s^2).

Source excerpts

“The construction successively removes neighborhoods from the remaining induced graph, until every remaining vertex has small neighborhood weight. Each removed part excludes a smaller clique, and the remainder has small edge mass. We then retain one part at random and divide its weights by that part's selection probability.” · Show in paper

Triangle peeling by successively deleting edges whose common-neighbor weight is less than τ\tau.

Source excerpts

“Starting with G, delete any edge whose common-neighbor weight in the current graph is less than tau, and continue until no such edge remains.” · Show in paper

Weighted random walks PuP_u, lazy walks Qu=(I+Pu)/2Q_u = (I + P_u)/2, and Kuj=PuQujK_u^j = P_u Q_u^j on neighborhoods N(u)N(u) with entropy increment smoothing.

Source excerpts

“On the finite set N(u) define stochastic matrices Pu(v, z) = wz 1_{vz in E(G)} / cuv, Qu = (I + Pu)/2, K_u^j = Pu Q_u^j (j >= 0).” · Show in paper

Shared rejection sampling of walk rows to group incident edges and split vertices into copies with bounded neighborhood weight while preserving the cross-mass bound.

Source excerpts

“We use the shared rejection construction of Kleinberg and Tardos [11, Section 3, Lemmas 3.1 and 3.2]. Angel and Spinka [4, Theorem 2 and Section 2.1] give the sharper pairwise disagreement estimate stated below.” · Show in paper