we-solve (beta)

Math-1564 · mathematics · Combinatorics

Finite-boundary transfer for infinite second neighborhoods

Status Partially solved · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $D=(V,E)$ be a nonempty, possibly infinite, oriented graph: there are no loops or parallel arcs and never arcs in both directions between two vertices. For a vertex $v$, let $N^+(v)$ and $N^-(v)$ be its sets of outgoing and incoming neighbours. Define \[ N_2^+(v)=\{w\notin N^+(v)\cup\{v\}:\exists u, v\to u\to w\}. \] Paths have finite length, and this set is precisely the vertices at shortest outgoing distance two. Call $D$ locally finite when both $N^+(v)$ and $N^-(v)$ are finite for every $v$. Call it out-locally finite when only $N^+(v)$ is required to be finite for every $v$; there need not be a uniform bound on these finite degrees.

The workshop asks two questions. Must every nonempty locally finite oriented graph have a vertex $v$ with $|N_2^+(v)|\ge|N^+(v)|$? Does the same conclusion hold for every nonempty out-locally finite oriented graph? The latter permits infinite indegrees and is the stronger assertion. In either class the second out-neighbourhood of a fixed vertex is finite, since it is contained in a finite union of finite first out-neighbourhoods. Thus the comparison is between finite integers, not infinite cardinalities. No countability, connectedness, or global finiteness is imposed on the vertex set. These are extensions of the finite second-neighbourhood problem to the two stated local finiteness conditions.

Short English statement

Does the second-neighbourhood conjecture remain valid for infinite locally finite graphs, or even when only each outdegree is finite?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1564-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-1564

Seymour second neighborhoods: The theorem resolves the finite subcase of both local-finiteness questions. It does not supply a witness in every possibly infinite locally finite or out-locally-finite graph; finite truncation can add boundary sinks and does not by itself establish the infinite assertion.

This page records partial support. Complete resolution of the catalogue question is not established by this record.

Finite-boundary transfer for infinite second neighborhoods

OpenAI's claim

Seymour second neighborhoods: The paper claims that every finite nonempty oriented graph has a vertex whose second out-neighborhood is at least as large as its first. The second neighborhood excludes vertices already reachable in one step.

Mathematical statement of the claimed result

Mathematical claim 1.
For a nonempty finite oriented graph $D$, with no loops or oppositely directed pair of edges, let $N_1^+(v)$ be the out-neighbors and $N_2^+(v)$ the vertices at directed distance exactly two. The claimed theorem gives \[\exists v\in V(D):\quad|N_1^+(v)|\le|N_2^+(v)|.\] For triangle-free $D$ a corollary yields a vertex with $d^+(v)\le|Z(v)|$ and $n-1\ge2d^+(v)+d^-(v)$, where $Z(v)$ consists of non-neighbors excluding $v$. Hence $\delta^+\ge n/3$ and $\delta^-\ge n/3$ force a directed triangle; a digraph regular in both directions with degree $r$ and girth four has $n\ge3r+1$. These consequences require the specified in-degree conditions and do not give the full out-degree-only Caccetta--Häggkvist assertion.

Outline of the argument

Seymour second neighborhoods: A smallest counterexample is pruned to yield strict neighborhood inequalities for all proper vertex sets. Replacing vertices by transitive tournaments strengthens these to a discrete concavity inequality. Extremal families of ordered pairs and an augmented bipartite matching are then controlled by two factorizations of one matrix, contradicting that inequality.

Formal verification

Family 173 describes Lean coverage for the exact second-out-neighborhood inequality for a suitable vertex of every finite nonempty oriented graph.

Seymour second neighborhoods: The manuscript links SeymourSecondNeighborhood.lean (declaration OAI.SeymourSecondNeighborhood.exists_goodVertex).

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →