Cover Image

A note on the computational complexity of weak saturation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Tancer, Martin, Tyomkyn, Mykhaylo
Format:	Preprint
Published:	2025
Subjects:	Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On plane rigidity matroids
by: Tyomkyn, Mykhaylo
Published: (2026)

The Brown-Erdős-Sós conjecture in dense triple systems
by: Santos, Giovanne, et al.
Published: (2025)

Alternating paths in oriented graphs with large semidegree
by: Skokan, Jozef, et al.
Published: (2024)

Pach's animal problem within the bounding box
by: Tancer, Martin
Published: (2024)

Two-block paths in oriented graphs of large semidegree
by: Penev, Irena, et al.
Published: (2025)

Unavoidable subgraphs in digraphs with large out-degrees
by: Hons, Tomáš, et al.
Published: (2025)

When does a tree activate the random graph?
by: Antonir, Asaf Cohen, et al.
Published: (2025)

Shellability is hard even for balls
by: Paták, Pavel, et al.
Published: (2022)

On the Small Quasi-kernel conjecture
by: Erdős, Péter L., et al.
Published: (2023)

Weak saturation rank: a failure of linear algebraic approach to weak saturation
by: Terekhov, Nikolai, et al.
Published: (2024)

A short proof of Tuza's conjecture for weak saturation in hypergraphs
by: Terekhov, Nikolai
Published: (2025)

Colorful fractional Helly theorem via weak saturation
by: Chakraborti, Debsoumya, et al.
Published: (2024)

Rational values of the weak saturation limit
by: Ascoli, Ruben, et al.
Published: (2025)

Asymptotically optimal lower bounds on weak saturation numbers for hypergraphs
by: Terekhov, Nikolai
Published: (2026)

The weak saturation number of $\boldsymbol{K_{2, t}}$
by: Miralaei, Meysam, et al.
Published: (2022)

Sequence saturation
by: Anand, et al.
Published: (2024)

A note on the Erdős Matching Conjecture
by: Martin, Ryan R., et al.
Published: (2024)

A note on strong Erdős-Hajnal for graphs with bounded VC-minimal complexity
by: Fu, Yayi
Published: (2023)

Infinite induced-saturated graphs
by: Bonamy, Marthe, et al.
Published: (2025)

Poset saturation of unions of chains
by: Ji, Shengjin, et al.
Published: (2025)

Rainbow saturation for complete graphs
by: Chakraborti, Debsoumya, et al.
Published: (2022)

Proper rainbow saturation for trees
by: Lane, Andrew, et al.
Published: (2024)

The rainbow saturation number is linear
by: Behague, Natalie, et al.
Published: (2022)

On the proper rainbow saturation numbers of cliques, paths, and odd cycles
by: Baker, Dustin, et al.
Published: (2024)

On saturation problems for matchings with regularity constraints
by: Yang, Gang, et al.
Published: (2025)

Halfway to induced saturation for even cycles
by: Fan, Xinyue, et al.
Published: (2025)

Some results on minimum saturated graphs
by: Zhang, Chenke, et al.
Published: (2025)

Induced saturation for complete bipartite posets
by: Liu, Dingyuan
Published: (2024)

Improved bounds for proper rainbow saturation
by: Lane, Andrew, et al.
Published: (2024)

Weak saturation of tensor product of cliques
by: Terekhov, Nikolai
Published: (2026)

Weak rainbow saturation numbers of graphs
by: Li, Xihe, et al.
Published: (2024)

Weak saturation numbers in random graphs
by: Kalinichenko, Olga, et al.
Published: (2023)

The complexity of computing the period and the exponent of a digraph
by: Kiefer, Stefan, et al.
Published: (2024)

Alternative set-theoretical algorithms for efficient computations of cliques in Vietoris-Rips complexes
by: de Souza, Danillo Barros, et al.
Published: (2025)

Generalized saturation game
by: Patkós, Balázs, et al.
Published: (2024)

Weak saturation numbers of large complete bipartite graphs
by: Akhmejanova, Margarita, et al.
Published: (2025)

The saturation number of wheels
by: Qiu, Yanzhe, et al.
Published: (2025)

A note on digraph splitting
by: Christoph, Micha, et al.
Published: (2023)

On the number of edges in saturated partial embeddings of maximal planar graphs
by: Barát, János, et al.
Published: (2025)

Minimum saturated graphs without $4$-cycles and $5$-cycles
by: Ma, Yue
Published: (2025)