Non-symmetry of biconstrained two-step reachability
Read the paper (PDF, 4 pages) · Source and verification (ZIP) · Zenodo record
Plain-English explanation · Read on this page · Collaboration
Abstract
The biconstrained reachability function ψ(x, y) is the largest fraction of the first part that some vertex of the third part must reach in two steps, over all finite tripartite graphs satisfying minimum-degree conditions in both directions on each adjacent pair. We answer its symmetry question negatively: |ψ(13/27, 14/27) − ψ(14/27, 13/27)| ≥ 1/108. The proof establishes the exact rational-boundary formula ψ(1 − θ, θ) = 1 − θ/d(θ), where d(θ) is a minimum integer degree of a positive rational regular incidence template. An existing seven-type example and its complement bound both relevant integers by four, making equality impossible. Neither exact value nor their ordering is needed or asserted.
The idea in plain English
Imagine three groups of vertices, with connections between neighboring groups. Each adjacent pair must meet a minimum connection requirement in both directions. How large a fraction of the first group must at least one vertex in the third group be able to reach in two steps?
Exchanging the two thresholds can change that guarantee. At thresholds 13/27 and 14/27, the guarantees differ by at least 1/108. This is a statement about all eligible finite graphs; looking at two individual examples would not suffice.
The surprising feature is that the proof establishes a definite gap without finding either exact guarantee or deciding which is larger. It obtains an exact boundary formula involving an integer, then uses a known small construction to restrict the possible integers.
The precise result
The graph is finite and simple, partitioned into nonempty stable parts A, B and C, with no A–C edges. An (x,y)-biconstrained graph satisfies all four conditions: every A vertex has at least x|B| neighbors in B; every B vertex has at least x|A| neighbors in A and y|C| neighbors in C; every C vertex has at least y|B| neighbors in B.
For each graph, take the largest fraction of A reachable from any single C vertex through B. Each reached A vertex is counted once, however many paths reach it. The function ψ(x,y) is the infimum of this maximum over all eligible finite graphs and partitions. It is the best universal guarantee; its attainment is not assumed in the definition.
The main separation is |ψ(13/27,14/27) − ψ(14/27,13/27)| ≥ 1/108. Neither exact value nor their ordering is asserted.
More generally, for every rational θ with 0 < θ < 1, the paper proves ψ(1−θ,θ) = 1−θ/d(θ), and this value is attained by a finite ordinary graph.
Here d(θ) is the minimum unweighted maximum row degree of a finite binary matrix M with distinct columns and strictly positive rational probability vectors b and q satisfying Mq = θ1 and Mᵀb = θ1. A row degree counts column types, not weighted mass. Rows may repeat and the matrix may be rectangular.
Why the result holds
On the boundary x+y=1, a vertex in C that misses a vertex in A forces their middle neighborhoods to be complementary. If the maximum reach is below one, this applies to every C vertex and forces exact degree equalities between B and C. Grouping identical neighborhoods produces a regular incidence template. The reverse degree condition from B to A bounds the smallest missed class, giving a lower bound valid for every finite graph.
For the matching upper bound, a template attaining the least integer degree gives weighted vertex types. Strictly positive middle weights preserve the paths between distinct types, and rational weights turn the construction into an ordinary finite graph by replacing types with integer numbers of vertices. This proves the formula and finite attainment.
The seven-type construction of Chudnovsky, Hompe, Scott, Seymour and Spirkl, together with its complement, gives d(13/27) ≤ 4 and d(14/27) ≤ 4. The formula then leaves only finitely many integer possibilities; none give equal guarantees, and every possible absolute gap is at least 1/108.
Scope and limitations
The boundary formula is stated for rational θ strictly between zero and one. The page makes no claim about irrational boundary parameters, the endpoints, or the full function away from this boundary.
The two integer minima, the two exact ψ-values and their ordering remain unevaluated here. The displayed finite graphs supply upper bounds only and are not claimed to attain the infima. The bound 1/108 is not claimed to be the exact gap.
All four degree inequalities and strict positivity of the rational template weights matter. The known symmetry of the related one-direction function φ is a different result. The inherited seven-type example is credited prior work; the contribution here is the universal rational-boundary formula and its quantitative asymmetry consequence. No exhaustive priority or current-openness certification is claimed.
Status and AI use
Research, proof development, computational checks, literature review and writing were extensively AI-assisted. This is an unrefereed preprint without external human peer review or formal proof-assistant verification. The archive includes the published source and exact computational controls.
Read the paper
Open PDF in a full window · Download the original from Zenodo
Collaborate on this result
I welcome collaboration with researchers in extremal graph theory who would like to examine the boundary formula, its incidence-template argument and relationship to earlier biconstrained results, or help prepare a journal submission.
Authorship and responsibilities would be discussed in relation to the substantive contributions made.
Cite this paper
Alec Kriebel. (2026). Non-symmetry of biconstrained two-step reachability (Version 1.0) [Preprint]. Zenodo. https://doi.org/10.5281/zenodo.23127646
Background and prior work
- Paul Seymour — Biconstrained graphs, Oberwolfach Report 1/2019: Printed pages 46–47 give the four degree conditions and ask whether ψ is symmetric.
- Chudnovsky, Hompe, Scott, Seymour and Spirkl — Concatenating Bipartite Graphs (2022): The finite weighted framework and Figure 1 supply the credited seven-type template. Theorem 2.3 concerns φ symmetry; Theorem 12.2 concerns a special minimal-value case for ψ.