Countable ultrahomogeneous undirected graphs 论文

摘要

Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G equals mathematical left-angle upper V Subscript upper G Baseline comma upper E Subscript upper G Baseline mathematical right-angle"> <mml:semantics> <mml:mrow> <mml:mi>G</mml:mi> <mml:mspace width="thinmathspace"/> <mml:mo>=</mml:mo> <mml:mspace width="thinmathspace"/> <mml:mrow> <mml:mo>⟨</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mspace width="thinmathspace"/> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>E</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:mo>⟩</mml:mo> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">G\, = \,\left \langle {{V_G},\,{E_G}} \right \rangle</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be an undirected graph. The complementary graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G overTilde"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>G</mml:mi> <mml:mo stretchy="false"> ~ </mml:mo> </mml:mover> </mml:mrow> <mml:annotation encoding="application/x-tex">\tilde G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mathematical left-angle upper V Subscript upper G Baseline comma upper E Subscript upper G overTilde Baseline mathematical right-angle"> <mml:semantics> <mml:mrow> <mml:mo>⟨</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mspace width="thinmathspace"/> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>E</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>G</mml:mi> <mml:mo stretchy="false"> ~ </mml:mo> </mml:mover> </mml:mrow> </mml:mrow> </mml:msub> </mml:mrow> </mml:mrow> <mml:mo>⟩</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\left \langle {{V_G},\,{E_{\tilde G}}} \right \rangle</mml:annotation> </mml:semantics> </mml:math> </inline-formula> where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis upper V 1 comma upper V 2 right-parenthesis element-of upper E Subscript upper G overTilde"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>V</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mspace width="thinmathspace"/> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>V</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mspace width="thinmathspace"/> <mml:mo> ∈ </mml:mo> <mml:mspace width="thinmathspace"/> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>E</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mover> <mml:mi>G</mml:mi> <mml:mo stretchy="false"> ~ </mml:mo> </mml:mover> </mml:mrow> </mml:mrow> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">({V_1},\,{V_2})\, \in \,{E_{\tilde G}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> iff <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper V 1 not-equals upper V 2"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>V</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mspace width="thinmathspace"/> <mml:mo> ≠ </mml:mo> <mml:mspace width="thinmathspace"/> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>V</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{V_1}\, \ne \,{V_2}</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="left-parenthesis upper V 1 comma upper V 2 right-parenthesis not-an-element-of upper E Subscript upper G"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>V</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mspace width="thinmathspace"/> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>V</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow>