**Problem of the Week**

**BUGCAT**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

**BingAWM**

**Math Club**

**Actuarial Association**

seminars:comb:abstract.200907rus

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.

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.

seminars/comb/abstract.200907rus.txt · Last modified: 2020/01/29 14:03 (external edit)

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported