Exact colorings of graphs
Status partial medium confidence
Beyond the Stacey-Weidl (1999) result that $P(c,m)$ fails for $c$ sufficiently large compared to $m\geq 3$, Narayanan (2014) gave a quantitative refinement showing that in any exact $k$-coloring of the edges of $K_{\mathbb N}$, the set of values $m$ for which an exactly $m$-colored complete infinite subgraph exists has size at least $\sqrt{2k}$, and this bound is tight for infinitely many $k$. Kittipassorn and Narayanan (2014, 2015) further proved a canonical Ramsey theorem answering related questions of Stacey and Weidl and an approximate version for hypergraphs. The original Erickson `if and only if' conjecture for the full range $3\leq m<c$ remains open in general.
Cited literature (3)
-
Shows that for any exact $k$-coloring of $K_{\mathbb N}$, the set of $m$ for which an exactly $m$-colored complete infinite subgraph exists has size at least $\sqrt{2k}$, with the bound tight for infinitely many $k$; refines Stacey-Weidl's partial answer to Erickson's conjecture.
-
Proves a canonical dichotomy for edge colorings of $K_{\mathbb N}$ with infinitely many colors (either every $m\in\mathbb N$ is achievable or one finds one of two canonical infinite substructures), answering a question of Stacey and Weidl and yielding new results on exactly $m$-colored complete subgraphs in finitely-colored cases.
-
Extends the analysis to hypergraphs: shows that in finite colorings using at least $m$ colors one can find an exactly $\hat m$-colored complete infinite sub-hypergraph for some $\hat m$ close to $m$, providing the natural hypergraph analogue of Erickson-type results.
Reviewer notes. The Erickson 'if and only if' conjecture as stated (P(c,m) holds iff m=1, m=2, or c=m) was not yet completely resolved by the post-2010 literature surveyed; Stacey-Weidl (1999, pre-posting) showed failure for c large vs m, and Narayanan (2014) gave a quantitative refinement. The full conjecture for the entire range 3<=m<c does not appear to be settled in either direction in the verified post-posting literature, so 'partial' is the appropriate status. Did not verify the journal-side DOI for the Approximations paper directly (Wiley returned 403); DOI 10.1002/jgt.21853 confirmed via DBLP and the author's publication list. arXiv ID for the hypergraph paper not located.
Discussion
Stacey and Weidl have shown that given $ m \geq 3 $ , there is an integer $ C(m) $ such that $ P(c,m) $ is false for all $ c \geq C(m) $ .
Bibliography
-
★
[?]M. Erickson, ``A Conjecture Concerning Ramsey's Theorem,'' Discrete Mathematics 126 , 395--398 (1994); MR 95b :05209 -
[?]A. Stacey and P. Weidl, "The Existence of Exactly m-Coloured Complete Subgraphs," J. of Combinatorial Theory , Series B 75 , 1-18 (1999)