A jump of the saturation number in random graphs? (Q6955983)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 8066816
Language Label Description Also known as
default for all languages
No label defined
    English
    A jump of the saturation number in random graphs?
    scientific article; zbMATH DE number 8066816

      Statements

      A jump of the saturation number in random graphs? (English)
      0 references
      0 references
      0 references
      0 references
      21 July 2025
      0 references
      For any graphs \(G\) and \(F\), a subgraph \(H\) of \(G\) is said to be \(F\)-saturated in \(G\) if it is a maximal \(F\)-free subgraph of \(G\). The least number of edges in an \(F\)-saturated subgraph of \(G\) is called the saturation number \(\operatorname{sat}(G,F)\). \textit{D. Korándi} and \textit{B. Sudakov} [ibid. 51, No. 1, 169--181 (2017; Zbl 1370.05191)] initiated the study of the saturation problem for random graphs, when the host graph \(G\) is the binomial random graph \(G(n,p)\) for a constant \(p\). In this paper, the authors raise the following conjecture: For a constant \(p\) in \((0,1)\) if \(F\) is a graph such that every \(e\) in \(E(F)\) belongs to a triangle in \(F\), then with high probability \(\operatorname{sat}(G(n,p),F)=o(n\ln n)\). They improve a solution to this conjecture by deriving a universal bound for \(\operatorname{sat}(G(n,p)\). Further, they also obtain a family of graphs for which the bound is linear in \(n\). Besides proving certain useful results, they also raise some open problems whose solution may come close to a full settlement of the above conjecture.
      0 references
      probablistic combinatorics
      0 references
      random graphs
      0 references
      saturation number
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references