Lucas Rusnak (Binghamton)

Oriented Hypergraphs

Abstract for the Combinatorics Seminar 2009 December 18

These lectures are the Ph.D. thesis defense of Mr. Rusnak. His examining committee is Laura Anderson, Gerard Cornuejols (Carnegie-Mellon), Marcin Mazur, and Thomas Zaslavsky (chair).

Everyone is welcome to attend.

Abstract

The linear dependencies of the columns of a 0,+1,−1-matrix play an important role in many combinatorial optimization problems. The dependencies are well understood through graph theory if each column has one +1 and one −1, and almost as well understood through signed graph theory if each column has at most two nonzero elements. I generalize these methods to a theory of oriented hypergraphs, whose hypergraph structure can be used to describe the column dependencies of many 0,+1,−1-matrices besides those that can be handled with graphs and signed graphs.

An oriented hypergraph is defined by an orientation of each incidence between an edge and a vertex, in a way that generalizes orientation of signed graphs. I develop oriented hypergraph structures, called “arteries”, “flowers”, and “cross-thetas”, that are analogous to paths, circles, and theta subgraphs in graphs and signed graphs.