top of page
Dr. Kathie Cameron, Wilfrid Laurier University
Dr. Kathie Cameron, Wilfrid Laurier University

Wed, Nov 24

|

ZOOM: 837 6398 9129 (wincom)

Dr. Kathie Cameron, Wilfrid Laurier University

Parity Theorems and Exchange Graph Algorithms concerning Paths, Cycles and Trees

Tickets are not on sale
See other events

Time & Location

Nov 24, 2021, 3:00 p.m. EST

ZOOM: 837 6398 9129 (wincom)

About the event

Parity Theorems and Exchange Graph Algorithms concerning Paths, Cycles and Trees

Carsten Thomassen and I proved that in any graph G, the number of cycles containing a specified edge as well as all the odd-degree vertices is odd if and only if G is eulerian. Where all vertices have even degree this is a theorem of Sunichi Toida and where all vertices have odd degree it is Andrew Thomason's generalization of Smith's Theorem.

Kenneth Berman extended Thomason’s Theorem to trees: he used a counting argument to prove that if T is a spanning tree of a graph G where all vertices in G-E(T) have odd degree, there is an even number of spanning trees of G with the same degree as T at each vertex.

I give a common generalization of these results to a parity theorem about (not necessarily spanning) trees.

Andrew Thomason proved his theorem by constructing a graph X(G), his lollipop graph, in which the odd-degree vertices correspond precisely to the things he wants to show there are an even number of, namely the hamiltonian cycles in G containing the specified edge. Christos Papadimitriou calls this approach the polynomial parity argument (PPA). It provides an algorithm for given one of the objects, finding another, by walking in X(G) from one odd-degree vertex to another.

I have extended Thomason's algorithm to one which, in a non-eulerian graph, finds a second cycle containing a specified edge and all the odd-degree vertices, and more generally finds a second tree with certain properties. I will discuss these algorithms and some other parity theorems.

Share this event

elsevier logo.png

Please consider supporting our initiatives by donating below. Your money will be used to continue to provide administrative support to our database and colloquium. Furthermore, your funds will help to provide scholarship funds for all of our current and future scholarships initiatives, including our 2021-2022 initiatives in Mexico and Africa. 

©2024 by Women in Combinatorics

We stand with #BlackLivesMatter and the AAPI community. View our full statement here.

bottom of page