2024/05/28 by Nikolai Terekhov, Terekhov, Nikolai, Maksim Zhukovskii +1 · 2 citations
Economics, Econometrics and Finance · #Combinatorics (math.CO) #Credit Risk and Financial Regulations #FOS: Mathematics
paper · doi:10.48550/arxiv.2405.17857
openalex publication_date 2024/05/28 · openalex created_date 2024/05/30 · openalex updated_date 2026/07/28
Given a graph F and a positive integer n, the weak F-saturation number wsat(Kn,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 Kn in such a way that, for every copy F'⊂ Kn of F, there exist non-zero λe, e∈ E(F'), satisfying ∑e∈ E(F')λe w(e)=0, then dimW≤ wsat(Kn,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(Kn,F). We also suggest a modification of this approach that allows to get tight lower bounds even when the original linear algebraic approach is not sufficient. Finally, we generalise our results to random graphs, complete multipartite graphs, and hypergraphs.