Oriented edge count between sets

PDF p. 18: Section 3 opening

Let $G=(V,E)$ be a finite undirected graph with nonempty vertex set, at most one edge between any pair of vertices, and possible self-loops. Its adjacency entry $A_{x,y}$ is $1$ if $\{x,y\}\in E$ and $0$ otherwise, with $\{x,x\}$ representing a loop. For subsets $X,Y\subseteq V$, define

$e(X,Y):={\sum }_{x\in X}{\sum }_{y\in Y}{A}_{x,y}\mathrm{.}$

This is an ordered-pair count: a non-loop edge with both endpoints in $X\cap Y$ contributes twice, while a loop at a vertex of $X\cap Y$ contributes once. If $X$ and $Y$ are disjoint, each edge with one endpoint in $X$ and the other in $Y$ contributes once. Write $X^c=V\setminus X$ for the set of vertices outside $X$.

Adjacency, degrees, graph Laplacian, and spectral notation

Finite symmetric networks and loop removal

Ordered edge counts and centered cut vectors

A finite sum in a commutative monoid indexed by an arbitrary finite set

The difference a ∖ b, the symmetric difference a △ b, and the complement X ∖ a relative to a set X

The intersection ⋂ x of a nonempty set, the binary intersection a ∩ b := ⋂{a,b}, and disjointness

The Cartesian product A × B := { z ∈ P(P(A ∪ B)) : ∃ a ∈ A ∃ b ∈ B z = (a,b) }

Given: A graph and subsets $X,Y$ as in the definition.

Goal: Verify that the count and complement are well defined and that the stated edge-counting conventions follow from the formula.

1.1 By [F1], $A$ is symmetric and nonnegative, so [F2] makes it a network. The two index sets are finite, and [F3] gives the ordered count as a well-defined finite sum, independent of any ordering used to enumerate them. By [F4], $X^c$ is precisely the complement of $X$ relative to $V$. [given, F1, F2, F3, F4]

2.1 By [F6], every nonzero summand corresponds to an ordered pair $(x,y)\in X\times Y$ whose endpoints form an edge. By [F5], $X\cap Y$ consists of vertices belonging to both sets, and disjointness means $X\cap Y=\mathrm{\varnothing }$. If distinct endpoints both lie in $X\cap Y$, both orders occur and contribute $1$ each; a loop there supplies only the single pair $(x,x)$. If $X\cap Y=\mathrm{\varnothing }$, a crossing edge has exactly one endpoint in $X$ and one in $Y$, so exactly one of its two orders lies in $X\times Y$, and no loop occurs. Thus the stated conventions follow. [F1, F5, F6, step 1.1] ∎

The notation and the convention that a loop contributes once to the degree are attributed to the opening of Section 3 of Expander graphs are globally synchronizing. The counting interpretation above follows from the displayed definition and the stated graph convention.