## Abstract

We prove a lower bound of Ω(n^{2}/log^{2}n) on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial f(x_{1},..,x_{n}). Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff ([34]), who proved a lower bound of Ω(n^{4/3}/log^{2}n) for the same polynomial. Our improvement follows from an asymptotically optimal lower bound for a generalized version of Galvin's problem in extremal set theory. A special case of our combinatorial result implies, for every n, a tight Ω(n) lower bound on the minimum size of a family F of subsets of cardinality 2n of a set X of size 4n, so that any subset of X of size 2n has intersection of size exactly n with some member of F. This settles a problem of Galvin up to a constant factor, extending results of Frankl and Rödl [15] and Enomoto et al. [12], who proved in 1987 the above statement (with a tight constant) for odd values of n, leaving the even case open.

Original language | English (US) |
---|---|

Pages (from-to) | 149-178 |

Number of pages | 30 |

Journal | Combinatorica |

Volume | 40 |

Issue number | 2 |

DOIs | |

State | Published - Apr 1 2020 |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics

## Keywords

- 03D15
- 68Q17
- 68R05
- 68W30