The strong saturation conjecture for bipartite graphs
The strong saturation conjecture for bipartite graphs
Let be the minimum number of edges in an bipartite graph such that adding any new edge between its two classes creates a copy of . Let denote the directed analogue, where the copies of have their vertices in the first class and their vertices in the second class. Strong saturation conjecture. For every there is an integer such that for every ,
The directed quantity is known to equal , while the displayed construction gives the stated upper bound for the undirected quantity. The conjecture asserts that this bound is best possible for sufficiently large , so the gain from allowing undirected copies is an additive constant.
Sources & referencesView supporting material
Primary source
Guy Moshkovitz and Asaf Shapira, “Exact Bounds for Some Hypergraph Saturation Problems”, arXiv:1209.3598 (2014).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.