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

No percolation at criticality on quasi-transitive graphs

For any infinite connected locally finite quasi-transitive undirected graph GG with pc(G)<1p_c(G) < 1, critical Bernoulli bond percolation has no infinite open cluster almost surely, i.e., Ppc(G)(there is an infinite open cluster)=0\mathbb{P}_{p_c(G)}(\text{there is an infinite open cluster}) = 0, or equivalently Ppc(G)(∣Cx∣=∞)=0\mathbb{P}_{p_c(G)}(|C_x| = \infty) = 0 for every vertex xx.

On an infinite connected locally finite quasi-transitive graph GG of subexponential growth, for every p∗>0p_* > 0 there is C<∞C < \infty (depending on GG and p∗p_*) such that Pp(Hs(e))≤Cs−1/2\mathbb{P}_p(H_s(e)) \le C s^{-1/2} for all e∈E(G)e \in E(G), s≥1s \ge 1, and p∗≤p<1p_* \le p < 1, where Hs(e)={Cx≠Cy,∣Cx∣≥s,∣Cy∣≥s}H_s(e) = \{C_x \neq C_y, |C_x| \ge s, |C_y| \ge s\}.

For the deterministic lazy depth-first search from ww towards BB under Bernoulli percolation μ\mu of parameter 0<p<10 < p < 1, the sum of weights W=∑e queried actual open pivotqdeW = \sum_{e \text{ queried actual open pivot}} q d_e satisfies EμW≤1\mathbb{E}_\mu W \le 1 and EμW2≤3\mathbb{E}_\mu W^2 \le 3.

For finitely many terminating deterministic adaptive query algorithms on a finite set of bits, if every bit is read by at most a≥1a \ge 1 algorithms on the support of QQ, then ∑iD(Qi∥μi)≤a22p(1−p)D(Q∥μ)\sum_i D(Q_i \| \mu_i) \le \frac{a^2}{2p(1-p)} D(Q \| \mu), where μ\mu is Bernoulli(pp) product law.

Under Bernoulli bond percolation μ\mu of parameter p∈(0,1)p \in (0, 1) on a finite undirected graph with a simple path x0,…,xdx_0, \dots, x_d (d≥2d \ge 2) satisfying μ(xj↔xk)≥c>0\mu(x_j \leftrightarrow x_k) \ge c > 0 for k−j<dk - j < d and μ(Cx0≠Cxd,∣Cx0∣,∣Cxd∣≥s)=δ>0\mu(C_{x_0} \neq C_{x_d}, |C_{x_0}|, |C_{x_d}| \ge s) = \delta > 0, there is a path edge ee with −log⁡μ(Hs(e))≤C(log⁡(1/δ)+⌈log⁡2d⌉+1)-\log \mu(H_s(e)) \le C(\log(1/\delta) + \lceil \log_2 d \rceil + 1).

If GG is an infinite connected locally finite quasi-transitive graph with pc<1p_c < 1, log⁡V+(r)=o(r)\log V_+(r) = o(r), and log⁡V−(r)/log⁡r→∞\log V_-(r)/\log r \to \infty, then critical Bernoulli bond percolation on GG has almost surely no infinite cluster.

For any countable graph GG with independent edge-open probabilities in [0,1][0, 1], a vertex oo, a nonempty set AA, and any set TT, P(o↔A,o↔T)≥P(o↔A)inf⁡a∈AP(a↔T)\mathbb{P}(o \leftrightarrow A, o \leftrightarrow T) \ge \mathbb{P}(o \leftrightarrow A) \inf_{a \in A} \mathbb{P}(a \leftrightarrow T).

If GG is an infinite connected locally finite quasi-transitive graph and V−(Rj)≤RjdV_-(R_j) \le R_j^d for some d<∞d < \infty and radii Rj→∞R_j \to \infty, then there exist a finite-index subgroup Λ≤Aut(G)\Lambda \le \mathrm{Aut}(G), a finitely generated nilpotent group NN, and an epimorphism ϱ:Λ→N\varrho: \Lambda \to N such that Λ\Lambda has finitely many vertex orbits, ker⁡ϱ\ker \varrho has finite vertex orbits, and ϱ(Λv)\varrho(\Lambda_v) is finite for every vv.

Let GG be an infinite connected locally finite graph of subexponential growth with pc(G)<1p_c(G) < 1. If a group Λ\Lambda acts by automorphisms with finitely many vertex orbits and admits an epimorphism ϱ:Λ→N\varrho: \Lambda \to N onto a finitely generated nilpotent group such that ker⁡ϱ\ker \varrho has finite vertex orbits and ϱ(Λv)\varrho(\Lambda_v) is finite for every vv, then Ppc(G)(∣Cv∣=∞)=0\mathbb{P}_{p_c(G)}(|C_v| = \infty) = 0 for all v∈Gv \in G.

Under the hypotheses of Proposition 8.1 (equivariant Z2\mathbb{Z}^2-coordinates, 0<pc<10 < p_c < 1, unique infinite cluster at pcp_c, no infinite open ray with bounded π\pi-projection), for every 0<e,η<1/100 < e, \eta < 1/10 there is mm such that for any ρ0>0\rho_0 > 0 there exist an invertible linear map Φ:R2→R2\Phi: \mathbb{R}^2 \to \mathbb{R}^2 and p′∈[pc/2,pc)p' \in [p_c/2, p_c) such that (t,z)=Φπ(t, z) = \Phi \pi has edge increments at most ρ0\rho_0 and Pp′(Es(y))≥1−η\mathbb{P}_{p'}(E_s(y)) \ge 1 - \eta for all y∈V(G)y \in V(G) and s∈{−1,1}s \in \{-1, 1\}.

In the fresh-collar setting of Proposition 9.2, P(∗↔B∗,∗↮T∗)≤κ\mathbb{P}(* \leftrightarrow B_*, * \nleftrightarrow T_*) \le \kappa.

Under the coordinate, corridor, and fresh-collar hypotheses and numerical bounds of Proposition 9.3, Bernoulli bond percolation at p′<pcp' < p_c has an infinite cluster with positive probability.

For nearest-neighbor Bernoulli bond percolation on Zd\mathbb{Z}^d, for every d≥2d \ge 2, there is almost surely no infinite cluster at the critical probability (in particular on Z3\mathbb{Z}^3).

Methods

Binary interpolation along a path using normalized contact weights and an inverse pivot-guessing procedure to bound the relative entropy of adjacent large distinct clusters.

Source excerpts

“We construct Qη by opening contacts along two chains of clusters. A reverse procedure that guesses and closes these contacts will account for the possible multiplicity of the opening map.” · Show in paper

Random-priority ordering with bit caching and shifted-Legendre polynomial endpoint bounds to control the relative entropy of overlapping adaptive query transcripts.

Source excerpts

“Assign independent uniform priorities in [0, 1] to the algorithms and run them in priority order, caching previously read bits.” · Show in paper

Triangular matrix inversion of conditional cluster columns combined with alternating cluster updates to establish a joint gluing inequality on countable graphs.

Source excerpts

“The weights come from the inverse of a triangular matrix of conditional cluster probabilities. A positivity property of its cluster columns will give both the required signs in the inverse and the displayed comparison.” · Show in paper

Induction on the number of infinite cyclic factors in a cyclic series of a nilpotent quotient supplied by Tessera-Tointon's finitary structure theorem to exclude infinite open rays with bounded projection.

Source excerpts

“We then prove the theorem by induction on a cyclic series of N. In the induction step, a component over a bounded coordinate box has a quotient with fewer infinite cyclic factors. This excludes rays with bounded projection; Sections 8 and 9 use the remaining rays to construct percolation below pc.” · Show in paper

Fresh-collar transfer and adaptive exploration with stored predictions along an oriented quadrant of separated corridors in quotient coordinates.

Source excerpts

“The corridors form the bonds of an oriented square lattice, but their vertex sets are coordinate preimages in G. All paths and revealed edges remain in G. We will reveal an incoming corridor only after estimating connections through the still fresh outgoing corridors.” · Show in paper