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 proof of Seymour’s second-neighborhood conjecture

Every nonempty finite oriented graph has a vertex vv such that ∣N1+(v)∣≤∣N2+(v)∣|N_1^+(v)| \le |N_2^+(v)|.

If Theorem 1.1 has a counterexample, then there is a finite nonempty oriented graph GG in which every vertex has positive indegree and ∣U∣+∣FG2(U)∣<2∣FG(U)∣|U| + |F_G^2(U)| < 2|F_G(U)| for every ∅≠U⊊V(G)\emptyset \neq U \subsetneq V(G).

If DD is a finite nonempty oriented graph with ∣N1+(v)∣>∣N2+(v)∣|N_1^+(v)| > |N_2^+(v)| for every v∈V(D)v \in V(D), chosen with minimum order and then minimum number of arcs, then DD is strongly connected, every vertex has positive indegree, and ∣F2(S)∖F(S)∣<∣F(S)∖S∣|F^2(S) \setminus F(S)| < |F(S) \setminus S| for every ∅≠S⊊V(D)\emptyset \neq S \subsetneq V(D).

Let DD be an oriented graph on n≥1n \ge 1 vertices, all of positive indegree, satisfying ∣F2(S)∖F(S)∣<∣F(S)∖S∣|F^2(S) \setminus F(S)| < |F(S) \setminus S| for every nonempty proper subset of V(D)V(D). Replacing each vertex by a transitive tournament on m>nm > n vertices and putting all arcs from the block at vv to the block at ww for each arc v→wv \to w of DD produces an oriented graph GG with all indegrees positive that satisfies ∣U∣+∣FG2(U)∣<2∣FG(U)∣|U| + |F_G^2(U)| < 2|F_G(U)| for every ∅≠U⊊V(G)\emptyset \neq U \subsetneq V(G).

For any finite set XX with a binary relation →\to and two families R,C⊆X×X\mathcal{R}, \mathcal{C} \subseteq X \times X, there exist conflict-free subfamilies R′⊆R\mathcal{R}' \subseteq \mathcal{R} and C′⊆C\mathcal{C}' \subseteq \mathcal{C} retaining every initially conflict-free member such that ∣R∖R′∣+∣C∖C′∣≤∣H∣+∣{z∈Z:z is covered by no member of R′∪C′}∣|\mathcal{R} \setminus \mathcal{R}'| + |\mathcal{C} \setminus \mathcal{C}'| \le |H| + |\{z \in Z : z \text{ is covered by no member of } \mathcal{R}' \cup \mathcal{C}'\}|.

If T⊆I×JT \subseteq I \times J for finite sets I,JI, J and D:RJ→RID : \mathbb{R}^J \to \mathbb{R}^I has maximum rank among all real matrices supported on TT, then for every x∈ker⁡Dx \in \ker D, every y∈ker⁡D⊤y \in \ker D^\top, and every (s,j)∈T(s, j) \in T, one has xjys=0x_j y_s = 0.

There is no nonempty finite oriented graph GG in which every vertex has an in-neighbor and whose one-step image operator F(U)F(U) satisfies ∣U∣+∣F2(U)∣<2∣F(U)∣|U| + |F^2(U)| < 2|F(U)| for every ∅≠U⊊V(G)\emptyset \neq U \subsetneq V(G).

For every nonempty finite oriented graph DD: (i) for every vertex weighting η:V(D)→[0,∞)\eta : V(D) \to [0, \infty), there is v∈V(D)v \in V(D) with η(N1+(v))≤η(N2+(v))\eta(N_1^+(v)) \le \eta(N_2^+(v)); (ii) there is a vertex weighting η:V(D)→[0,∞)\eta : V(D) \to [0, \infty) with ∑x∈V(D)η(x)=1\sum_{x \in V(D)} \eta(x) = 1 such that η(N1+(v))≤η(N2+(v))\eta(N_1^+(v)) \le \eta(N_2^+(v)) for every v∈V(D)v \in V(D); and (iii) for every arc weighting w:A(D)→[0,∞)w : A(D) \to [0, \infty), there is v∈V(D)v \in V(D) with ∑s∈V(D)βvw(s)≥∑u∈N1+(v)w(vu)\sum_{s \in V(D)} \beta_v^w(s) \ge \sum_{u \in N_1^+(v)} w(vu).

For any nonempty finite oriented graph DD of order nn: (i) if DD has no directed 3-cycle, some vertex vv satisfies d+(v)≤∣Z(v)∣d^+(v) \le |Z(v)| and n−1≥2d+(v)+d−(v)n - 1 \ge 2d^+(v) + d^-(v); (ii) if δ+(D)≥n/3\delta^+(D) \ge n/3 and δ−(D)≥n/3\delta^-(D) \ge n/3, then DD contains a directed 3-cycle; and (iii) if DD is rr-regular (r≥1r \ge 1) with directed girth four, then n≥3r+1n \ge 3r + 1.

Methods

Minimal-counterexample reduction combined with a transitive-tournament lexicographic blowup D[Tm]D[T_m] (m>∣V(D)∣m > |V(D)|) to amplify a subset deficit ∣F2(S)∖F(S)∣<∣F(S)∖S∣|F^2(S) \setminus F(S)| < |F(S) \setminus S| into a strict subset inequality ∣U∣+∣FG2(U)∣<2∣FG(U)∣|U| + |F_G^2(U)| < 2|F_G(U)|.

Source excerpts

“There are two steps. Minimality first gives a strict deficit for subsets of a counterexample. Replacing each vertex by a sufficiently large transitive tournament then turns that deficit into (2).” · Show in paper

“The construction below is the lexicographic product D[T_m], where T_m is a transitive tournament.” · Show in paper

Bounding a maximum matching in an augmented bipartite graph Γ\Gamma via generic matrix rank, simultaneous polynomial nonvanishing, and kernel restrictions at maximum support rank (Lemma 3.2), followed by König's theorem to obtain a pruning of two conflicting families of pairs.

Source excerpts

“The proof will bound a matching in an augmented bipartite graph by using matrix ranks.” · Show in paper

“Our choice of coefficients uses the correspondence between generic matrix rank and maximum matching size [9, Section 5, Theorem 1].” · Show in paper

Extremal optimization over compatible pairs of families P,Q⊆V(G)×V(G)P, Q \subseteq V(G) \times V(G) containing the diagonal Δ\Delta, maximizing ∣P∣+∣Q∣+d|P| + |Q| + d where dd is the number of uncovered points, and applying complementation and pruning to derive a contradiction.

Source excerpts

“Thus we may choose, among all compatible pairs with \Delta \subseteq P \cap Q, one maximizing M + d, where M = |P| + |Q|, d = |X|^2 - |F_1 P| - |F_2 Q|.” · Show in paper