6. classifying sets of graphs

problem

For each of the following sets of $\mathsf{Graphs}$, determine whether it is meager, comeager, or neither, as well as whether it is null, conull, or neither with respect to the fair coin-flip measure.

1. $\mathsf{Bip}≔\{G∈\mathsf{Graphs}:\text{\(G\) is bipartite}\}$
2. $\mathsf{Conn}≔\{G∈\mathsf{Graphs}:\text{\(G\) is connected}\}$
3. $\mathsf{Mat}≔\{G∈\mathsf{Graphs}:\text{\(G\) is has a perfect matching}\}$

---

1. claim

   $\mathsf{Bip}$ is nowhere dense (and therefore meager).

   proof

   We wish to show that given any non-empty open set $U⊆\mathsf{Graphs}$ there exists a non-empty open $V⊆U$ such that $V∩\mathsf{Bip}=∅$. It suffices to show this for just basic open sets, i.e. finitely-determined sets.

   Let $U⊆\mathsf{Graphs}$ be finitely-determined. That is to say, membership in $U$ depends only on whether a graph contains edges among some fixed finite set $I⊂\{\{u,v\}:u,v∈ℕ,\;u≠v\}$. Let $n∈ℕ$ be so large that it isn’t incident to any of the edges in $I$; i.e., membership in $U$ doesn’t depend on any edges involving $n$.

   Then let $V=\{G∈U:\text{\(G\) contains the triangle \(\{n,n+1,n+2\}\)}\}$, which is non-empty. And notice that no graphs in $V$ are bipartite since they contain a triangle (odd cycle).

   claim

   $\mathsf{Bip}$ is null.

   proof

   For each $n∈ℕ$ let

   $$T_n=\{G∈\mathsf{Graphs}:\text{\(G\) doesn’t contain the triangle \(\{3n,3n+1,3n+2\}\)}\},$$

   and let $S=⋂_{n∈ℕ} T_n$. Observe that $\mathsf{Bip}⊆S$ since every bipartite graph must be triangle-free. Also observe that the $k$-th partial intersection has measure

   $$μ\left(\smash{\underbrace{⋂_{n≤k} T_n}_{≕S_k}} \vphantom{⋂_k}\right) \vphantom{\underbrace{\left(⋂_k\right)}_S} = \left(\frac 7 8\right)^{k+1}.$$

   Then $μ(\mathsf{Bip})≤μ(S)≤μ(S_k)=(7/8)^{k+1}$. By sending $k→∞$ we obtain $μ(\mathsf{Bip})=0$.

2. claim

   $\mathsf{Conn}$ is comeager.

   proof

   We will show that $\mathsf{Conn}$ is dense and $G_δ$.

   • Dense: Fix any finitely-determined $U⊆\mathsf{Graphs}$. Let $n∈ℕ$ be large enough so that no edges involving $n$ affect membership in $U$. Let $G∈U$, and add edges $\{k,n\}$ for all $k≠n$ to obtain a new graph $G'$. Since membership in $U$ is unaffected by edges involving $n$, we have that $G'∈U$ as well. And also $G'$ is connected because all vertices are adjacent to $n$.
   • $G_δ$: For each pair $i,j∈ℕ$, define $$S_{ij}=\{G∈\mathsf{Graphs}:∃\text{path between \(i\) and \(j\) in \(G\)}\}.$$ By writing $$S_{ij}=⋃_{p∈ℕ^*} \{G∈\mathsf{Graphs}:\text{\(p\) is a path between \(i\) and \(j\) in \(G\)}\}$$ observe that $S_{ij}$ is open. And also observe that connectedness means exactly that all pairs of vertices are joined by some path, i.e. $\mathsf{Conn}=⋂_{i,j∈ℕ}S_{ij}$.

   claim

   $\mathsf{Conn}$ is conull.

   proof

   Fix any distinct $i,j∈ℕ$, and define

   $$S_{ij}=\{G∈\mathsf{Graphs}:\text{there are no paths between \(i\) and \(j\) in \(G\)}\}.$$

   Next for every $k∈ℕ∖\{i,j\}$ define

   $$T_{ijk}=\{G∈\mathsf{Graphs}:\text{\(i∼k∼j\) is not a path in \(G\)}\}.$$

   Note that $S_{ij}⊆⋂_{k∈ℕ∖\{i,j\}} T_{ijk}$, so $μ(S_{ij})≤(3/4)^n$ for all $n∈ℕ$, and therefore $μ(S_{ij})=0$.

   Meanwhile observe that $G∈\mathsf{Conn}^∁$ iff there exist $i,j∈ℕ$ not connected by a path; i.e.,

   $$\mathsf{Conn}^∁ = ⋃_{i≠j∈ℕ} S_{ij}.$$

   By countable (sub-)additivity $μ(\mathsf{Conn}^∁)≤∑μ(S_{ij})=0$.