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 ∑e∈ E(F')λₑ 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 limn→∞wsat(Kₙ,F)/n is not integer. Finally, we generalise our results to random graphs, complete multipartite graphs, and hypergraphs.