Back to search

University of Waterloo

Algebraic Methods for Reducibility in Nowhere-Zero Flows

Abstract

dc:description.abstract

We study reducibility for nowhere-zero flows. A reducibility proof typically consists of showing that some induced subgraphs cannot appear in a minimum counter-example to some conjecture. We derive algebraic proofs of reducibility. We define variables which in some sense count the number of nowhere-zero flows of certain type in a graph and then deduce equalities and inequalities that must hold for all graphs. We then show how to use these algebraic expressions to prove reducibility. In our case, these inequalities and equalities are linear. We can thus use the well developed theory of linear programming to obtain certificates of these proof. We make publicly available computer programs we wrote to generate the algebraic expressions and obtain the certificates.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2007

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Li, Zhentao

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/3307

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Li, Zhentao. Algebraic Methods for Reducibility in Nowhere-Zero Flows. University of Waterloo, 2007. http://hdl.handle.net/10012/3307