Introduction to Ramsey Theory and Set Theory Foundations

The Six-Vertex Theorem and Ramsey Theory Foundations

• The Complete Graph with Five Vertices ($K_5$):

  • In a scenario with five vertices, any two points can be connected by an edge.

  • The total number of edges resulting from connecting all pairs of five vertices is $10$.

  • If each edge is colored with one of two available colors, there are $2^{10}$ (or $1024$) possible colorings.

  • It is possible to color the $10$ edges of a five-vertex graph such that no monochromatic triangle exists. A monochromatic triangle is a set of three vertices where all three edges connecting them are the same color.

• The Six-Vertex Assertion:

  • Precise Mathematical Statement: Given six vertices and two available colors, if every edge connecting any two vertices is colored, there necessarily exists at least one monochromatic triangle.

  • Implication for Groups of People: In a group of six people, where any two people are either mutual acquaintances (one color) or mutual strangers (the second color), there must exist a subgroup of three people who are either all mutual acquaintances or all mutual strangers.

• Importance of Precise Statements and Proofs:

  • Mathematical statements must be precise to avoid ambiguity and to understand their logical implications.

  • A "stunning statement" must be supported by a proof to distinguish between "math or myth."

  • Logic is the only way to ascertain truth and understand why certain conditions (like the specific number of vertices) are necessary for a conclusion to hold.

Proof of the Six-Vertex Theorem

• Step 1: Selecting a Fixed Point:

  • Pick a single random vertex from the six available vertices. Let this vertex be denoted as $v$.

  • Since every pair of vertices is connected, there are exactly five edges branching out from vertex $v$ to the remaining five vertices.

• Step 2: Applying the Pigeonhole Principle:

  • Let the two colors be Blue ($B$) and Red ($R$).

  • The total number of edges connected to $v$ is $5$. Therefore, $B + R = 5$, where $B$ and $R$ are non-negative integers representarive of the count of edges of each color.

  • Possible distributions for $(B, R)$ are $(0, 5), (1, 4), (2, 3), (3, 2), (4, 1),$ or $(5, 0)$.

  • In every possible case, at least one of the colors must have a count of at least $3$. If both were less than $3$ ($2$ or fewer), the total count would be at most $2 + 2 = 4$, which contradicts the fact that there are $5$ edges.

  • Conclusion: At least three of the five edges originating from vertex $v$ must be the same color.

• Step 3: Examining the Neighbors:

  • Suppose, without loss of generality, that at least three edges originating from $v$ are Blue.

  • Let the vertices at the other ends of these three Blue edges be denoted as $V_1, V_2,$ and $V_3$.

• Step 4: Evaluating the Internal Edges of the Subgroup:

  • Consider the three edges that connect the vertices $V_1, V_2,$ and $V_3$ to each other (forming a triangle among themselves).

  • Case A: If any one of the edges connecting $V_1, V_2,$ or $V_3$ is Blue (e.g., the edge connecting $V_1$ and $V_2$ is Blue), then a Blue triangle is formed by that edge and the two Blue edges connecting those vertices back to vertex $v$.

  • Case B: If none of the edges connecting $V_1, V_2,$ and $V_3$ are Blue, then all three edges forming that triangle ($V_1-V_2$, $V_2-V_3$, and $V_3-V_1$) must be Red.

  • Conclusion: In either case, a monochromatic triangle (either Blue or Red) is unavoidable.

• Failure of the Proof for Five Vertices:

  • When the number of vertices is reduced to five, vertex $v$ is only connected to the remaining four vertices.

  • In this case, $B + R = 4$. This allows for a distribution where $B = 2$ and $R = 2$.

  • Because it is not guaranteed that three edges share the same color, the subsequent argument for completing a monochromatic triangle fails.

  • This demonstrates that the specific requirement of six vertices is a necessary hypothesis for the theorem to be true.

Introduction to Set Theory

• Basic Definition of a Set:

  • A set is defined as a collection of objects.

  • This notion was historically complex; mathematicians at the beginning of the 20th century struggled with the logical paradoxes arising from defining a set as "any collection of objects."

• Roster Notation:

  • Sets can be represented by enclosing a list of elements within a pair of brackets: $\{ ... \}$.

  • Example of a Finite Set: $X = \{0, 1, 6\}$. This set contains three members or elements.

  • Order Independence: The order in which elements are listed within the brackets does not change the identity of the set. Values can be listed in any sequence.

  • Example of an Infinite Set: $Y = \{1, 3, 5, 7, 9, \dots\}$. The use of ellipses indicates that the pattern continues indefinitely.

• Set Membership Symbols:

  • Membership ($\in$): This symbol indicates that an object is a member of a specific set. For example, $0 \in X$ and $3 \in Y$.

  • Non-membership ($\notin$): This symbol is the negation of the membership symbol. For example, $0 \notin Y$ and $3 \notin X$.

  • In the expression $a \in S$, the item preceding the symbol ($a$) is the element, and the item following the symbol ($S$) is the set.

Subsets and Proper Subsets

• Subset ($\subseteq$):

  • A set $S$ is considered a subset of set $X$ if every member of $S$ is also a member of $X$.

  • Example: If $S = \{0, 1\}$ and $X = \{0, 1, 6\}$, then $S \subseteq X$.

  • Self-Membership: Every set is naturally a subset of itself ($X \subseteq X$) because every member of $X$ is a member of $X$.

• Proper Subset ($\subset$ or $\subsetneq$):

  • A set $S$ is a proper subset of $X$ if two conditions are met:

    1. $S$ is a subset of $X$ ($S \subseteq X$).

    2. $S$ is not equal to $X$ ($S \neq X$).

  • This implies there must be at least one element in $X$ that is not present in $S$. In the example above, $S = \{0, 1\}$ is a proper subset of $X = \{0, 1, 6\}$ because the element $6$ is in $X$ but not in $S$.

• Set Equality:

  • If it is true that $S \subseteq X$ and also true that $X \subseteq S$, then the two sets must be equal ($S = X$) because they contain the exact same collection of elements.