Ramsey Numbers
=============

In graph theory, the Ramsey number R(m, n) represents the smallest number such that any graph with this many vertices contains either a complete subgraph with m vertices or an independent subgraph with n vertices.

Example: R(3, 3) = 6. This means that in any graph with 6 vertices, there must be either a triangle (complete 3-vertex subgraph) or an independent set of 3 vertices.

Note: Calculating Ramsey numbers is extremely challenging, and only a few exact values have been determined to date.

Sample code for visualizing a graph with 5 vertices::

    # Importing the NetworkX graph library
    import networkx as nx
    import matplotlib.pyplot as plt

    # Creating a graph with 5 vertices
    G = nx.Graph()
    
    # اضافه کردن یالها
    G.add_edges_from([(1,2), (1,3), (2,3), (2,4), (3,5), (4,5)])
    
    # نمايش گراف
    nx.draw(G, with_labels=True, node_color='lightblue')
    plt.show()

.. image:: images/ramsey.png

Note: This is a simplified example of modeling a Ramsey problem in Python. In practice, investigating higher Ramsey numbers requires more sophisticated algorithms and intensive computations.

.. _trees:

Introduction  
------------

A **tree** is a connected acyclic graph. Below is an example of tree representation in code:

.. code-block:: python

    class TreeNode:
        def __init__(self, data):
            self.data = data
            self.children = []
    
    def print_tree(root):  # Prints the tree
        if not root:
            return
        print(root.data)
        for child in root.children:
            print_tree(child)

.. image:: /images/tree-example.png

Trees have wide applications in data structures and algorithms. A tree with ``n`` nodes has exactly ``n-1`` edges. For example, the tree in the image above has 5 nodes and 4 edges. Key properties include:

- There is exactly one unique path between any two nodes  
- Adding any edge creates a cycle  
- Removing any edge disconnects the graph

.. rst-class:: arabic-direction

First Problem
~~~~~~~~~~~~~

We have a group of 6 people where every two are either friends or enemies. Prove that there exist three people who are either all mutual friends or all mutual enemies.

Definition
~~~~~~~~~~

The function :math:`R(a,b)` is equal to the smallest :math:`n` such that no matter how we color the edges of a :math:`K_n` with two colors, blue and red, there will either be a blue :math:`K_a` or a red :math:`K_b`.

You can easily prove that the above problem is equivalent to demonstrating the statement :math:`R(3,3) \leq 6`.

Bounds
---------------

Obtaining the exact value of :math:`R(a,b)` is not possible, but we can provide bounds for it.

First, we must prove that :math:`R(a, b)` exists. (It might be that for no :math:`n`, the desired property holds for :math:`K_n`)

The solution idea is to find a vertex with sufficiently many blue or red adjacents, then consider only its neighbors and find a smaller blue or red clique there.

More precisely, suppose there exists a vertex :math:`u` with at least :math:`R(a-1,b)` blue neighbors. In this case, considering its neighbors leads to two scenarios:

- There exists a blue :math:`K_{a-1}` among them, in which case adding vertex :math:`u` creates a blue :math:`K_a`.
- There exists a red :math:`K_b` among them.

Therefore, if there exists a vertex with at least :math:`R(a-1,b)` blue neighbors, the problem is solved. Similarly, if there exists a vertex with at least :math:`R(a, b-1)` red neighbors, the problem is also solved.

Thus, we conclude that :math:`R(a,b) \leq R(a-1,b) + R(a,b-1)`. Because if our graph has at least :math:`R(a-1,b) + R(a,b-1)` vertices, any arbitrary vertex will either have sufficiently many blue neighbors or sufficiently many red neighbors.

This inequality reminds us of Pascal's identity ( :math:`\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}` ).

Furthermore, we can prove by induction that :math:`R(a, b) \leq \binom{a+b}{a}`.

.. code-block:: rst

   Generalization to k Dimensions
   ------------------------------

   Suppose we have an n-element set, and we have colored each of its k-element subsets with either blue or red. We call a subset :math:`A` a **k-dimensional cluster** if all k-element subsets of :math:`A` have the same color (if blue, we call it a blue cluster; if red, a red cluster).

   We define :math:`R_k(a,b)` as the minimum :math:`n` such that no matter how we color the k-element subsets of an n-element set with blue and red, there will either be a blue cluster of size :math:`a` or a red cluster of size :math:`b`.

   **Proof idea**: Similar to the previous approach. Assume :math:`n = R_k(a,b)`. Consider a specific element :math:`u` from the n-element set :math:`A`. Let :math:`B = A - \{u\}`. Color each :math:`(k-1)`-element subset :math:`S` of :math:`B` with the color of the k-element subset :math:`S \cup \{u\}`. If the size of :math:`B` is at least :math:`R_{k-1}( R_k(a-1,b), R_k(a,b-1) )`, then one of the following must occur:

   - :math:`B` contains a :math:`(k-1)`-dimensional blue cluster :math:`S` of size at least :math:`R_k(a-1,b)`. In this case, either :math:`S` contains a :math:`k`-dimensional red cluster of size :math:`b` (solving the problem), or :math:`S` contains a :math:`k`-dimensional blue cluster of size :math:`a-1`. We can then add :math:`u` to this cluster to form a :math:`k`-dimensional blue cluster of size :math:`a`.

   - :math:`B` contains a :math:`(k-1)`-dimensional red cluster :math:`S` of size at least :math:`R_k(a,b-1)`. In this case, either :math:`S` contains a :math:`k`-dimensional blue cluster of size :math:`a` (solving the problem), or :math:`S` contains a :math:`k`-dimensional red cluster of size :math:`b-1`. We can then add :math:`u` to this cluster to form a :math:`k`-dimensional red cluster of size :math:`b`.

   Based on this reasoning, we can prove that :math:`R_k(a,b) \leq R_{k-1}(R_k(a-1,b),R_k(a,b-1))`.

Generalization to k Dimensions and c Colors
--------------------------------------------

Similarly, we can formulate and prove the problem for more than two colors. We leave finding bounds on :math:`R_k(a_1,a_2,...,a_c)` to the reader.