digraph_cut_count
def
e_G(A, B): the number of edges of the digraph G from a vertex of A to a vertex of B.
Statement
def digraph_cut_count {V : Type*} [Fintype V] (G : Digraph V) [DecidableRel G.Adj] (A B : Finset V) : ℕ
- Defined in
- arXiv:2610.21381 (Optimally large cuts in both directions), Sec. 1 (notation e_G(A, B)).
- Verified
- 16 Oct 2026
- Axioms
- none listed
- Used by 17
- digraph_apex_over_bidirected_complete_out_degreeEvery vertex of D_d has outdegree at least d.
- digraph_both_cuts_ge_ceil_div_six_of_high_indegreeCase 1 of the proof of Theorem 1.4: in a loopless digraph with m arcs, if a vertex z has in-degree at least m/3 + 1 and some set A₀ ∋ z…
- digraph_both_cuts_ge_ceil_div_six_of_casesIf a finite digraph G admits a vertex subset A with both directed cut counts e(A, Aᶜ) and e(Aᶜ, A) at least ⌈m/6⌉ whenever some vertex has…
- tournament_cut_add_cut_compl_eq_sum_out_countIn any directed graph T on vertex set Fin n and for any subset S of vertices, the number of directed edges within S plus the number of…
- digraph_cut_sub_cut_eq_sum_net_degreeFor any vertex subset A in a finite digraph G, the directed cut count e(A, Aᶜ) minus e(Aᶜ, A) equals the sum over vertices v in A of the…
- digraph_apex_over_bidirected_complete_two_has_bipartitionThere exists a vertex bipartition V = A ⊔ B of the apex digraph D₂ on 4 vertices such that both directed cut counts e(A, B) and e(B, A)…
- tournament_directed_cut_eq_of_outdegrees_eqLet T₁ and T₂ be tournaments on vertex set Fin n such that every vertex v has the same outdegree in T₁ and T₂. Then for every subset S ⊆…
- digraph_apex_over_bidirected_complete_three_has_bipartitionThere exists a vertex bipartition V = A ⊔ B of the apex digraph D₃ on 5 vertices such that both directed cut counts e(A, B) and e(B, A)…
- digraph_both_cuts_ge_ceil_div_six_of_two_partitionsIf two vertex partitions have combined crossing count at least m and combined absolute directed-cut imbalance at most m/3, one partition…
- digraph_min_cut_eq_half_sum_sub_half_abs_diffFor any two vertex subsets A and B in a finite digraph G, the minimum of the directed cut counts e(A, B) and e(B, A) in ℚ equals half…
- digraph_apex_over_bidirected_complete_three_max_min_cutFor d = 3 (m = 16 arcs), every bipartition of D_3 has a directed cut of size at most 4 = ⌈2m/10⌉, so the bound of Conjecture 6.1 of…
- digraph_edge_count_eq_cut_addFor any vertex set A, the edges of a digraph split into those inside A, from A to its complement, from the complement to A, and inside the…
- digraph_min_cut_additive_bound_fails_for_every_dFor every d ≥ 2 there is a loopless digraph with minimum outdegree at least d and m = (d + 1)² arcs in which every vertex bipartition A ⊔…
- digraph_apex_over_bidirected_complete_min_cut_leFor every vertex set A of D_d, min(e(A, Aᶜ), e(Aᶜ, A)) ≤ ⌊(d + 1)²/4⌋.
- tournament_cut_count_self_eq_choose_twoIn any tournament T on vertex set Fin n and for any subset S of vertices, the number of directed edges with both endpoints in S equals…
- tournament_cut_count_eq_subIn any tournament T on vertex set Fin n and for any subset S of vertices, the directed cut size from S to its complement Sᶜ equals the sum…
- digraph_apex_over_bidirected_complete_edge_countD_d has (d + 1)² arcs.
Lean source view module on GitHub
/-- `e_G(A, B)`: the number of arcs `u → v` of `G` with `u ∈ A` and `v ∈ B`. -/ def digraph_cut_count {V : Type*} [Fintype V] (G : Digraph V) [DecidableRel G.Adj] (A B : Finset V) : ℕ := ((A ×ˢ B).filter fun p => G.Adj p.1 p.2).card