Rocky Mountain Algebraic Combinatorics Seminar

On Finding Obstructions for Consecutive-Ones matrices and Interval Graphs

Ross McConnell
Colorado State University

The intersection graph of a collection of sets has one vertex for each set in the collection, and an edge between two vertices if the sets intersect. A graph is an interval graph if it is the intersection graph of a set of intervals on a line. A characterization of interval graphs was given by Lekkerkerker and Boland in 1962, in terms of the set of minimal forbidden induced subgraphs for the class. A linear-time algorithm for recognizing whether a graph is an interval graph was given in 1976 by Booth and Lueker. We give the first efficient algorithm for finding one of Lekkerkerker and Boland's forbidden subgraphs when a graph is not an interval graph. Our algorithm runs in time linear in the size of the graph. A binary matrix has the consecutive-ones property if there exists an ordering of its columns, such that, in every row, the 1's form a consecutive block. A linear-time algorithm to determine whether a binary matrix has this property was a key step in Booth and Lueker's algorithm. The talk is based on joint work with Nathan Lindzey.


Classifying Semifields via Semilattices

Anton Betten
Colorado State University

A semifield is almost a field, except possibly for the axiom of associativity of multiplication (thus, the multiplicative structure is what is known as a loop). The classification of finite fields has been achieved by the second half of the 19-th century, and is now part of any serious algebra course, even at the undergraduate level. On the other hand, no comparable result is known for finite semifields. In fact, the situation is much more complex, with many known constructions and even more known examples that are presently sporadic (meaning there is no general construction that would explain the presence of the example). We discuss an approach to the classification of finite semifields by computer. We look at groups acting on semilattices and reformulate the problem of classifying semifields in this setting. Of course, this talk would not be complete without mentioning the recent computational results by Rúa and his collaborators. Parallel computing on a very large scale has been used to classify semifields for orders that are small but not too small to ignore.


Weber 223
4–6 pm
Friday, February 21, 2014
(Refreshments in Weber 117, 3:30–4 pm)
Colorado State University

This is a joint Denver U / UC Boulder / UC Denver / U of Wyoming / CSU seminar that meets biweekly. Anyone interested is welcome to join us at a local restaurant for dinner after the talks.

PDF version

Previous Seminars:

November 22, 2013
Justin Hughes, Josh Maglione

Department of Mathematics
Fort Collins, Colorado 80523