printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

****************************

math 269 - combinatorics seminar

sam spiro

ucsd

maximal independent sets in clique-free graphs

abstract:

an independent set $i$ of a graph $g$ is said to be a maximal independent set (mis) if it is maximal with respect to set inclusion. nielsen proved that the maximum number of mis's of size $k$ in an $n$-vertex graph is asymptotic to $(n/k)^k$, with the extremal construction being a disjoint union of $k$ cliques with sizes as close to $n/k$ as possible. in this talk we study how many mis's of size $k$ an $n$-vertex graph $g$ can have if $g$ does not contain a clique $k_t$. we prove for all fixed $k$ and $t$ that there exist such graphs with $n^{\lfloor\frac{(t-2)k}{t-1}\rfloor-o(1)}$ mis's of size $k$ by utilizing recent work of gowers and b. janzer on a generalization of the ruzsa-szemer\'edi problem. we prove that this bound is essentially best possible for triangle-free graphs when $k\le 4$. \medskip this is joint work with xiaoyu he and jiaxi nie.

host: jacques verstraete

october 5, 2021

4:00 pm

apm 6402 (halkin room)

****************************