Asymptotic equivalence of the edge functions for uniform systems

Let rr and tt be integers with r3r\geq 3 and trt\geq r. For an (r,t)(r,t)-system (H,F)(H,\mathcal{F}), let er,t(s)e_{r,t}(s) be the minimum of e(H)e(H) over systems with F=s|\mathcal{F}|=s, and let er,t(s)e_{r,t}'(s) be the corresponding minimum over maximal systems. The notation f(s)g(s)f(s)\asymp g(s) means that the two functions have the same order of magnitude. Asymptotic edge-function conjecture. For all integers r3r\geq 3 and trt\geq r,

er,t(s)er,t(s).e_{r,t}(s)\asymp e_{r,t}'(s).

This compares arbitrary and maximal (r,t)(r,t)-systems and predicts that imposing maximality does not change the asymptotic edge requirement.

Sources & referencesView supporting material

Primary source

Asier Calbet, “Twin-free K_r-saturated Graphs and Maximally Independent Sets in K_3-free Graphs”, arXiv:2411.19267 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.