Davies’s theorem and the coloring number of graphs

We generalize Davies’s famous example to a property of graphs: a graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis upper V comma upper X right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>V</mml:mi> <mml:mo>,</mml:mo> <mml:mi>X</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(V,X)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is <italic>Davies</italic> if for every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper F colon upper X right-arrow double-struck upper R"> <mml:semantics> <mml:mrow> <mml:mi>F</mml:mi> <mml:mo>:</mml:mo> <mml:mi>X</mml:mi> <mml:mo stretchy="false"> → </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">F:X\to \mathbb {R}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , there is a collection <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet g Subscript v Baseline colon v element-of upper V EndSet"> <mml:semantics> <mml:mrow> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>v</mml:mi> </mml:msub> <mml:mo>:</mml:mo> <mml:mi>v</mml:mi> <mml:mo> ∈ </mml:mo> <mml:mi>V</mml:mi> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\{g_v:v\in V\}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="omega right-arrow double-struck upper R"> <mml:semantics> <mml:mrow> <mml:mi> ω </mml:mi> <mml:mo stretchy="false"> → </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\omega \to \mathbb {R}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> functions such that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper F left-parenthesis v comma w right-parenthesis equals sigma-summation Underscript n greater-than omega Endscripts g Subscript v Baseline left-parenthesis n right-parenthesis g Subscript w Baseline left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>F</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>v</mml:mi> <mml:mo>,</mml:mo> <mml:mi>w</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:munder> <mml:mo> ∑ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mi> ω </mml:mi> </mml:mrow> </mml:munder> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>v</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:msub> <mml:mi>g</mml:mi> <mml:mi>w</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">F(v,w)=\sum _{n&gt;\omega } g_v(n)g_w(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet v comma w EndSet element-of upper X"> <mml:semantics> <mml:mrow> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mi>v</mml:mi> <mml:mo>,</mml:mo> <mml:mi>w</mml:mi> <mml:mo fence="false" stretchy="false">}</mml:mo> <mml:mo> ∈ </mml:mo> <mml:mi>X</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\{v,w\}\in X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We show that if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper C normal o normal l left-parenthesis upper X right-parenthesis less-than-or-equal-to omega 1"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">C</mml:mi> <mml:mi mathvariant="normal">o</mml:mi> <mml:mi mathvariant="normal">l</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>X</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo> ≤ </mml:mo> <mml:msub> <mml:mi> ω </mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {Col}(X)\leq \omega _1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartAbsoluteValue upper X EndAbsoluteValue less-than-or-equal-to German c"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mi>X</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow>