Weak saturation rank: a failure of linear algebraic approach to weak saturation

Given a graph F and a positive integer n, the weak F-saturation number wsat (Kₙ, F) is the minimum number of edges in a graph H on n vertices such that the edges missing in H can be added, one at a time, so that every edge creates a copy of F. Kalai in 1985 introduced a linear algebraic approach that became one of the most efficient tools to prove lower bounds on weak saturation numbers. If W is a vector space spanned by vectors w (e) assigned to edges e of Kₙ in such a way that, for every copy F' Kₙ of F, there exist non-zero ₑ, e E (F'), satisfying ₄ ₄ (₅') ₑ w (e) =0, then dimW wsat (Kₙ, F). In this paper, we prove limitations of this approach: we show infinitely many F such that, for every vector space W as above, dimW<wsat (Kₙ, F). It follows from the fact that the maximum possible dimension of such a vector space equals aFn+O (1) for some integer aF. We then suggest a modification of this approach that allows to get tight lower bounds even in the case when ₍wsat (Kₙ, F) /n is not integer. Finally, we generalise our results to random graphs, complete multipartite graphs, and hypergraphs.