## Discrete Math Seminar: Cedric Chauve

- Date: 04/10/2012
- Time: 14:30

Simon Fraser University

Certificates and spectral approach for the Consecutive-Ones Property

Abstract:

A binary matrix satisfies the Consecutive-Ones Property (C1P) if its

columns can be ordered in such a way that, on each row, the entries 1

are consecutive. Deciding if a matrix satisfies the C1P canbe done in

linear time, and several algorithms exist that can answer this question,

some quite intricated (such as the PQ-tree algorithm of Booth andLueker

(1976)).

In the first part of the talk, I will discuss the notionof non-C1P

certificate: given a matrix M, if an algorithm "answers" that Mis not

C1P, how can we check that this answer is correct ? In other word,can we

provide a structure (certificate) that can be used to validate easily

the answer of the algorithm. The first certificate for the C1P was

proposed in 2004 by McConnell but relies on an auxiliary structure, the

incompatibility graph of M. However, in 1972, Tucker proved that a

matrix is not C1Pif and only if it does contain some submatrix that

belong to 5 well characterized families, which defines a natural notion

of non-C1P certificate. Until recently, it was thought that the result

of Tucker was of little algorithmic interest. Here I will show that,

using an algorithmic technique calledpartition refinement, one can find a

Tucker pattern in a non-C1P matrix inlinear time and space.

In the second part, I will present a result of Atkins, Boman and

Hendrickson that shows that a spectral approach can be usedto decide if a

matrix is C1P. More precisely, let L be the Laplacian of M^t M. If M is

C1P, ordering the columns of M according to the order of entries of an

eigenvector of the second smallest eigenvalue of L makes all entries 1

consectuive in each row. Although computationally inefficient, this

spectral approach raises several questions that I will introduce.

These are works in collaboration with Tamon Stephen, Mehrnoush Malekesmaeili, Maria Tamayo, Ashok Rajaraman.

For more information please visit SFU Mathematics Department