Alphabeta Math
DefinitionDefinition: Literature-sourcedProof: Not applicableSession-authored (Fable 5 assisted)audited 2026-08-02
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced — the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted — a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated — a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Bipartite neighbourhoods, Hall's condition and systems of distinct representatives

Definition

Let GG be a finite bipartite graph with specified parts XX and YY. For SXS\subseteq X, its neighbourhood in YY is N(S):={yY:xyE(G) for some xS}.N(S):=\{y\in Y:xy\in E(G)\text{ for some }x\in S\}. The pair (X,Y)(X,Y) satisfies Hall's condition (on XX) if N(S)S|N(S)|\ge |S| for every SXS\subseteq X.

For any indexed family (Ax)xX(A_x)_{x\in X}, write U:=xXAxU:=\bigcup_{x\in X}A_x. A system of distinct representatives (SDR) is an injection r:XUr:X\to U such that r(x)Axr(x)\in A_x for every xXx\in X.

When XX and UU are finite, the incidence graph of the family is the finite bipartite graph with the disjoint tagged parts XL:={(x,L):xX},UR:={(u,R):uU}.X_{\mathrm L}:=\{(x,\mathrm L):x\in X\},\qquad U_{\mathrm R}:=\{(u,\mathrm R):u\in U\}. and an edge (x,L)(u,R)(x,\mathrm L)(u,\mathrm R) exactly when uAxu\in A_x. For SXS\subseteq X, its left tagged copy has neighbourhood N(SL)={(u,R):uxSAx}.N(S_{\mathrm L})=\{(u,\mathrm R):u\in\bigcup_{x\in S}A_x\}.

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 33 results over 16 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources