Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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.