Graphs, matrices, nullspaces and nowhere-zero bases

11/01/2016 - 12:15pm
11/01/2016 - 1:10pm
Shahriar Shahriari (Pomona College)

Let k be a fixed small positive integer and let A be a matrix. Can you find a basis for the nullspace of A consisting of vectors whose entries are from the set {±1, ±2, . . . , ±(k − 1)}? We conjecture that the answer is yes, if A is the (0, 1)–incidence matrix of a finite graph and if k = 5. If true, this would strengthen a celebrated conjecture of Tutte from the 1950s. In this talk, we discuss the conjecture, and, present positive results for a variety of graphs including the complete graphs. Joint work with Saieed Akbari and Amir Hossein Ghodrati.

Millikan 2099, Pomona College