Name
Abstract | ||
|---|---|---|
The t-colored rainbow saturation number rsat(t)(n, F) is the minimum size of a t-edgecolored graph on n vertices that contains no rainbow copy of F, but the addition of any missing edge in any color creates such a rainbow copy. Barrus et al. conjectured that rsat(t)(n, K-s) = Theta(n log n) for every s >= 3 and t >= ((s)(2)). In this short note we prove the conjecture in a strong sense, asymptotically determining the rainbow saturation number for triangles. Our lower bound is probabilistic in spirit, and the upper bound is based on the Shannon capacity of a certain family of cliques. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1137/17M1155429 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
rainbow saturation,Shannon capacity,cross-intersecting families | Discrete mathematics,Graph,Binary logarithm,Combinatorics,Saturation (chemistry),Vertex (geometry),Upper and lower bounds,Rainbow,Channel capacity,Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 2 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dániel Korándi | 1 | 2 | 3.45 |