Odd disjoint trails and totally odd graph immersions

I have succesfully defended my PhD thesis! It's "packed" with results on graph immersions with parity restrictions, and "covers" odd edge-connectivity, totally odd clique immersions, and a new submodular measure that's intimately connected with both.

Odd disjoint trails and totally odd graph immersions. Ross Churchley (2017). The odd edge-connectivity between two vertices in a graph is the maximum number $\lambda_o(u, v)$ of edge-disjoint $(u,v)$-trails of odd length. In this thesis, we define the perimeter of a vertex-set, a natural upper bound for the odd edge-connectivity between some of its constituent pairs. Our central result is an approximate characterization of odd edge-connectivity: $\lambda_o(u, v)$ is bounded above and below by constant factors of the usual edge-connectivity $\lambda(u, v)$ and/or the minimum perimeter among vertex-sets containing $u$ and $v$.

The relationship between odd edge-connectivity and perimeter has many implications, most notably a loose packing–covering duality for odd trails. (In contrast, odd paths do not obey any such duality.) For Eulerian graphs, we obtain a second, independent proof of the packing–covering duality with a significantly better constant factor. Both proofs can be implemented as polynomial-time approximation algorithms for $\lambda_o(u, v)$. After observing that perimeter satisfies a submodular inequality, we are able to prove an analogue of the Gomory–Hu Theorem for sets of minimum perimeter and, consequently, to construct an efficient data structure for storing approximate odd edge-connectivities for all vertex pairs in a graph.

The last part of the thesis studies more complicated systems of odd trails. A totally odd immersion of a graph $H$ in another graph $G$ is a representation in which vertices in $H$ correspond to vertices in $G$ and edges in $H$ correspond to edge-disjoint odd trails in $G$. Using our perimeter version of the Gomory–Hu Theorem, we describe the rough structure of graphs with no totally odd immersion of the complete graph $K_t$. Finally, we suggest a totally odd immersion variant of Hadwiger’s Conjecture and show that it is true for almost all graphs.

You can also read two papers published based on my results:

• Weak duality for packing edge-disjoint odd trails
• A submodular measure and approximate Gomory–Hu theorem for packing odd trails

or look at the slides I used at my defence.

I am grateful to NSERC for funding my degree with a Alexander Graham Bell Canada Graduate Scholarship, and to my supervisor Bojan Mohar.