====== 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.


----