A geometric version of the Andrásfai-Erdős-Sós theorem

Publication date 4 September 2014

Abstract: For each odd integer

k g e 5

, we prove that, if

M

is a simple rank-

r

binary matroid with no odd circuit of length less than

k

and with

| M | > k 2^{r - k + 1}

, then

M

is isomorphic to a restriction of the rank-

r

binary affine geometry; this bound is tight for all

r g e k - 1

. We use this to give a simpler proof of the following result of Govaerts and Storme: for each integer

n g e 2

, if

M

is a simple rank-

r

binary matroid with no

P G (n - 1, 2)

-restriction and with

| M | > l e f t (1 - f r a c 11 2^{n + 2} i g h t) 2^{r}

, then

M

has critical number at most

n - 1

. That result is a geometric analogue of a theorem of Andrasfai, Erdos, and Sos in extremal graph theory.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: A geometric version of the Andrásfai-Erdős-Sós theorem