Alphabeta Math
DefinitionDefinition: Literature-sourcedProof: Not applicableaudited 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 G be a finite bipartite graph with specified parts X and Y. For S⊆X, its neighbourhood in Y is N(S):={y∈Y:xy∈E(G) for some x∈S}. The pair (X,Y) satisfies Hall's condition (on X) if ∣N(S)∣≥∣S∣ for every S⊆X.

For any indexed family (Ax)x∈X, write U:=⋃x∈XAx. A system of distinct representatives (SDR) is an injection r:X→U such that r(x)∈Ax for every x∈X.

When X and U are finite, the incidence graph of the family is the finite bipartite graph with the disjoint tagged parts XL:={(x,L):x∈X},UR:={(u,R):u∈U}. and an edge (x,L)(u,R) exactly when u∈Ax. For S⊆X, its left tagged copy has neighbourhood N(SL)={(u,R):u∈⋃x∈SAx}.

Depends on

Used by

Dependency tree · two levels

13 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources