Infinite Monochromatic Subgraphs (Model theoretic aspects of the notion of independence and dimension)

全文

(1)34. 数理解析研究所講究録第2002巻 2016年 34-38. Infinite Monochromatic. Subgraphs. Akito Tsuboi. University. (Joint. of Tsukuba. work with Kota. Takeuchi). Introduction. 1. Proofs. are. not. given here. See [5] for the details. First Ramsey:. we. recall the. following. famous theorems of \bullet. Finite. Ramsey. Theorem. (FRT). \forall x, y, z\in $\omega$\exists z\in $\omega$[z\rightarrow(x)_{z}^{y}]. \bullet. Infinite. Ramsey Theorem (IRT). \foral x, y\in $\omega$[ $\omega$\rightar ow( $\omega$)_{y}^{x}]. To. explain structural Ramsey theory,. where A and B. are. we. introduce the notation. first order structures.. \left(\begin{ar ay}{l B\ A \end{ar ay}\right)=. the set of all. copies of A. in B.. Then, FRT for y=2(\forall x, y, z\in $\omega$\exists z\in $\omega$[z\rightarrow(x)_{z}^{2}]) following statement:. (^{*}). \left(\begin{ar y}{l B\ A \end{ar y}\right),. is. equivalent. to the. complete finite graphs A and z\in $\omega$ there is a complete finite f : [D]^{2}\rightarrow z is a finite coloring of the edges in D graph then there is A'\in\left(\begin{ar ay}{l D\ A \end{ar ay}\right) for which f([A']^{2}) is a singleton. For all. D such that if. In addition to. (^{**}). this, IRT for. x=2(\forall y\in $\omega$[ $\omega$\rightarrow( $\omega$)_{y}^{2}]). is. equivalent. to. For every infinite complete graph G and a finite edge coloring f : [G]^{2}\rightarrow y there is an infinite complete subgraph H\subset G such that f([H]^{2}) is a. singleton..

(2) 35. Ramsey theorem (finite version or infinite version) trivially provides edge colorings of complete graphs. Structural Ramsey theory studies Ramsey type results on more general structures other than complete graphs. So the classical results. on. Ramsey Class. 2. Let L be. a. relational. language and. K. a. assume. We. class of finite L ‐structures. \cdot. \cdot. K satisfies the conditions of Fra issé. so. that K has the Fra issé limit. \mathcal{M}. Definition 1 \bullet. (Ramsey Class).. K is. a. Ramsey class. s.t. for every. \forall A, B\in K, \forall n\in $\omega$, \exists C\in K. n. if. ‐coloring. f:\left(\begin{ar ay}{l C\ A \end{ar ay}\right)\rightar own B'\in\left(\begin{ar ay}{l} C\ B \end{ar ay}\right). there is. Example 2. In following classes \bullet. in which FRT holds. The. sets. The limit \mathcal{M} is. K_{2}= the class of linearly ordered finite. isomorphic. (hyper)graphs.. \mathcal{M} is the. graph.. K_{3}= the class of linearly ordered triangle‐free finite graphs.. The fact that are. a. \mathbb{Q}.. ordered random \bullet. is monochromatic.. Ramsey class is a class examples of Ramsey classes.. sense,. are. \left(\begin{ar y}{l B'\ A \end{ar y}\right). K_{1}= the class of linearly ordered finite to. \bullet. a. for which. found in Now. we. K_{1} is. [1], [2]. a or. Ramsey class follows from FRT. Proofs for K_{2} and K3. [3].. consider infinite versions of the above. prove statements like: For all n\in $\omega$ and. examples. We. want to. A\in K,. \mathcal{M}\rightar ow(\mathcal{M})_{n}^{A}, words, this arrow statement states that if every nisomorphic to A is painted in one of the colors \{0. where \mathcal{M} is the limit of K substructure of M ,. .. In. ,. ,. .. .. .. ,.

(3) 36. 1},. then there is. isomorphic. a. to A , is. substructure M'\cong M such that every substructure of M', pained in the same color. For K=K_{1} (linear orders), this. type of infinite version is. true.. In. fact,. this version is not true in. general,. even. it is. a. if K is. paraphrase of IRT. However, Ramsey.. Example 3. Let K be the class of all finite linearly ordered graphs. (This K is K_{2} in the example 2.) Then the limit \mathcal{M} is a linearly ordered random graph. Let \{a_{i}:i\in $\omega$\} be an enumeration of \mathcal{M} and let c:E(\mathcal{M})\rightarrow 2 be an edge coloring defined by: for edges \{a_{i}, a_{j}\},. c(\{a_i},a_{j}\)= left\{ begin{ar y}{l 1a_{i}<^{\mathcal{M}a_{j}\mathrm{a}\mathrm{n}\mathrm{d}i<j,\ 0\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}. \end{ar y}\right. Then \mathcal{M} has To. see. no. this, let D\subset \mathcal{M}. be infinite.. such that a_{i}, a_{j}, a_{k}\in D and. c(\{a_{k}, a_{j}\})=0. Remark 4 sion of RT \bullet. (An. Let K be each. easy. clearly A,. a. Then there must. \mathcal{M}\models a_{i}<a_{k}<a_{j}. argument using. .. Then. compactness).. c(\{a_{i}, \mathrm{a} \}). The. =1 while. following. weak. ver‐. holds.. Ramsey. \cdot. class. Let M be the Fra issé limit of K. B\in K and each finite. such that. homogeneous for c. be i<j<k\in $\omega$. infinite substructure D\cong \mathcal{M} that is. \left(\begin{ar y}{l B'\ A \end{ar y}\right). coloring f. :. \left(\begin{ar ay}{l M\ \mathcal{A} \end{ar ay}\right)\rightar own. ,. Then for. .. there is. B'\in\left(\begin{ar ay}{l} M\\ B \end{ar ay}\right). is monochromatic.. Infinite Version. 3. We work. k ‐partite. graphs, A is k ‐partite graph \{U_{i}(*)\}_{i<k}. on. 1. the universe of M is the 2.. R^{M}. is the set of all. 3. there is. no. edge. where k is finite. an. L=\{R(*, *)\}\cup. L ‐structure M such that. disjoint. edges. Let. union of. U_{i}^{M}(i<k) ;. in M ;. between two elements in the. \displaystyle \bigwedge_{i<k}\foral x, y(U_{i}(x)\wedge U_{i}(y)\rightarrow\neg R(x, y. same. part.. M\models.

(4) 37. U_{2}. U_{1}. U_{0}. .. .. Let K be the class of all finite k ‐partite a. k ‐partite random. U_{k-2}U_{k-1}. .. graphs.. It has the limit \mathcal{M} , called. graph.. (triangle‐free). graph and f be a finite coloring on the edges. There is a k‐partite‐induced subgraph N\cong \mathcal{M} such that f is partwise almost constant on N in the following sense: For each a\in N there is a finite subset X\subset N such that Theorem 5. Let \mathcal{M} be. a. k ‐partite. random. ax\cong_{L}ay\Rightarrow f(ax)=f(ay) From this. we can. easily deduce the following famous. Corollary 6 (Nešetřil‐ Rödl). Let K graphs. For any B\in K there is C\in K c on. C there is. .. B'\in\left(\begin{ar ay}{l} C\ B \end{ar ay}\right). such that. c. be the set. such that. is constant. results:. of all totally ordered finite for any finite edge‐coloring. on. B.. Corollary 7 (Nešetřil). Let K be the set of all totally ordered triangle‐ free finite graphs. For any B\in K there is C\in K such that for any finite edge‐coloring c on C there is B'\in\left(\begin{ar ay}{l} C\ B \end{ar ay}\right) such that c is constant on B.. References [1]. Jaroslav Nešetřil and. Vojtěch Rödl,. Partitions of finite relational and set. systems, Journal of Combinatorial Theory, Series A Volume 22, Issue 3,. 1977, 289‐312. [2] [3]. Harrington, Models Without cernibles, J. Symbolic Logic Volume 43, Issue 3 (1978), 572‐600. Fred G. Abramson and Leo A.. Slawomir tions and. Indis‐. Solecki, Direct Ramsey theorem for structures involving rela‐ functions, J. Comb. Theory, Ser. A 01/2012; 119:440‐449..

(5) 38. [4]. Saharon. [5]. Kota Takeuchi and Akito. edges,. Shelah, http: // arxiv. \mathrm{o}\mathrm{r}\mathrm{g}/\mathrm{a}\mathrm{b}\mathrm{s}/\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{h}/0504197 Tsuboi, Infnite subgraphs with monochromatic. submitted.. Institute of Mathematics. University. of Tsukuba. Ibaraki 305‐8571 Email address:. Japan [email protected].

(6)