A numerical equivalent of the four color map problem. (Q2601265)

Verf. stellt der üblichen Formulierung des Vierfarbenproblems (Problem I) folgende damit gleichwertige Probleme an die Seite: II: Man trianguliere die beiden durch ein \(n\)-Eck bestimmten Gebiete der Ebene durch ``Diagonalen'', die einander nicht schneiden. Lassen sich die Polygonecken (bei jeder Wahl der Triangulation) mit vier Farben färben, so daß (durch Seiten oder Diagonalen) verbundene Ecken verschiedene Farben erhalten? III: Eine Menge von Paaren ganzer Zahlen \((p_1, q_1),\ldots, (p_s, q_s)\) heiße eine \(n\)-zulässige Paarmenge, wenn \[ 0\leqq p_i, \quad p_i+2\leqq q_i, \quad q_i \leqq n \qquad (i=1,2,\ldots, s) \] und niemals \[ p_i<p_j<q_i<q_j; \] sie heißt vollständig, wenn man unter Einhaltung dieser Bedingungen kein weiteres Paar hinzufügen kann. Zwei vollständige \(n\)-zulässige Paarmengen bestehen aus gleich vielen Paaren. Kann man, wenn zwei vollständige \(n\)-zulässige Paarmengen \((p_i,q_i)\) und \((p_i', q_i')\) gegeben sind, Zahlen \(b_0,\ldots, b_n\) aus der Folge 1, 2, 3, 4 so bestimmen, daß \[ b_i \neq b_{i+1},\quad b_{p_i}\neq b_{q_i}, \quad b_{p_i'}\neq b_{q_i'}? \] IV: Eine Summe \(a_1 + a_2 + \cdots + a_n\) heiße geordnet, wenn man durch Einfügen von Klammern das Ausrechnen der Summe auf sukzessive Addition von je zwei Summanden zurückgeführt hat; alle beim schrittweisen Ausrechnen einer geordneten Summe auftretenden Zahlen (einschließlich der \(a_{\nu}\) selbst) heißen Partialsummen. Kann man, wenn die Summe \(a_1 + \cdots + a_n\) auf zwei Arten geordnet ist, die Unbestimmten \(a_{\nu}\) als ganze Zahlen so spezialisieren, daß keine der Partialsummen der beiden Anordnungen durch 4 teilbar ist? V: Für ein \(n\)-Eck \(P_n\) seien \(T_1,\ldots, T_{\tau_n}\) die Triangulationen des Inneren durch einander nicht schneidende Diagonalen; \(S_i\) sei die Gesamtheit der für \(T_i\) zulässigen Färbungen \(D_1^i,\ldots,D_{\delta_i}^i\) der Ecken von \(P_n\) mit vier Farben. Haben je zwei Systeme \(S_i\), \(S_j\) eine zulässige Färbung \(D_{\varrho}^i=D_{\sigma}^j\) gemeinsam? VI: \(\varDelta_1,\ldots,\varDelta_{\nu_n}\) seien die zulässigen Färbungen der Ecken des (noch nicht triangulierten) \(P_n\) (s. V.) mit vier Farben. Man bilde eine Matrix \[ (\eta_{ij}), \quad i=1,2,\ldots,\tau_n, \quad j=1,2,\ldots,\nu_n \quad \text{ mit } \quad \eta_{ij}=1 \quad \text{ oder } \quad 0, \] je nach dem \(\varDelta_j\) ein \(D_{\nu}^i\) ist oder nicht. Sind keine zwei Zeilen von \((\eta_{ij})\) orthogonal? Daß I mit II äquivalent ist, hat Verf. in einer früheren Arbeit (Ann. Math., Princeton, (2) 32 (1931), 378-390; JFM 57.0727.*) gezeigt; V und VI sind als andere Formulierungen von II erkennbar; die Äquivalenz von II mit III und von III mit IV wird hier bewiesen. An VI knüpft Verf. einige wahrscheinlichkeitstheoretische Betrachtungen, die bei hoher Länderzahl eine sehr geringe Wahrscheinlichkeit für die Existenz einer Karte, die sich nicht mit vier Farben färben läßt, ergeben.