Davies’s theorem and the coloring number of graphs
Proceedings of the American Mathematical Society · 13.04.2026 · 154 (6) · 2659-2667
DOI: 10.1090/proc/16540 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the American Mathematical Society, online erschienen am 13.04.2026. Verfasst von Péter Komjáth. Die Arbeit nennt 14 Literaturangaben.
Abstract (Originalsprache)
We generalize Davies’s famous example to a property of graphs: a graph ( V , X ) (V,X) is Davies if for every F : X → R F:X\to \mathbb {R} , there is a collection { g v : v ∈ V } \{g_v:v\in V\} of ω → R \omega \to \mathbb {R} functions such that F ( v , w ) = ∑ n > ω g v ( n ) g w ( n ) F(v,w)=\sum _{n>\omega } g_v(n)g_w(n) for { v , w } ∈ X \{v,w\}\in X . We show that if C o l ( X ) ≤ ω 1 \mathrm {Col}(X)\leq \omega _1 and | X | ≤ c |X|\leq \mathfrak {c} , then X X is Davies. On the other hand, there is a non-Davies graph X X with | X | = c + |X|=\mathfrak {c}^+ , C o l ( X ) = 3 \mathrm {Col}(X)=3 . If C h r ( X ) > c Chr(X)>\mathfrak {c} or C o l ( X ) > c + \mathrm {Col}(X)>\mathfrak {c}^+ , then X X is not Davies. If the existence of a supercompact cardinal is consistent, then so is that c = ℵ 3 \mathfrak {c}=\aleph _3 and any graph X X with C o l ( X ) > ω 1 \mathrm {Col}(X)>\omega _1 is not Davies.
Zitieren
APA
Komjáth, P. (2026). Davies’s theorem and the coloring number of graphs. Proceedings of the American Mathematical Society, 154(6), 2659-2667. https://doi.org/10.1090/proc/16540
Vancouver
Komjáth P. Davies’s theorem and the coloring number of graphs. Proceedings of the American Mathematical Society. 2026;154(6):2659-2667. doi:10.1090/proc/16540
BibTeX
@article{Komjth2026,
author = {Komjáth, Péter},
title = {Davies’s theorem and the coloring number of graphs},
journal = {Proceedings of the American Mathematical Society},
year = {2026},
volume = {154},
number = {6},
pages = {2659--2667},
doi = {10.1090/proc/16540}
}
EUVIMED