Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Graphs of large affine dimension

Algebra & Discrete Mathematics

Speaker: David Rolnick, MIT
Location: 1147 MSB
Start time: Mon, Oct 20 2014, 12:10PM

The affine dimension of a graph G (over R) is the smallest d such that G is the intersection graph of some collection of affine subspaces in $R^d$. Previously, no graphs had been known to have affine dimension greater than 4. Pudlak and Rodl demonstrated that the existence of graphs with large affine dimension implies the existence of Boolean functions of high complexity, and they asked for an explicit construction of such graphs. We consider the affine dimension of pseudorandom graphs, which we show can be made arbitrarily large.