Edge-bearing part embeds as a subgraph
DefinitionSparseDisc_Supplement_EdgeEmbedsIntograph-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-discrepancy
The edge-bearing part of a graph embeds into a graph if its non-isolated vertices inject into and every edge maps to an edge. Isolated vertices of are suppressed.
Definition code
import Mathlib
namespace SparseDisc.Supplement
/-- The edge-bearing part of `F` is isomorphic to a subgraph of `T`; isolated vertices of `F` are
ignored. This is the convention used for the omitted-edge graphs in Theorem 8.35
(Zeng–Cao–Dai–Wang–Liao, *Sparse Discrepancy Beyond Additive Functions*, STOC 2027 submission
manuscript (sha256 0f09ec60…25b81), p.45). -/
def EdgeEmbedsInto {V W : Type} (F : SimpleGraph V) (T : SimpleGraph W) : Prop :=
∃ φ : V → W, Set.InjOn φ {v | (F.neighborSet v).Nonempty} ∧
∀ u v, F.Adj u v → T.Adj (φ u) (φ v)
end SparseDisc.Supplement
Source
Zeng–Cao–Dai–Wang–Liao, Sparse Discrepancy Beyond Additive Functions, STOC 2027 submission (manuscript sha256 0f09ec60…), Theorem 8.35, p.45