.. _sphx_glr_api_gallery_combinatorics_extremal:

Extremal combinatorics
----------------------

Ramsey's theorem and the Erdős-Szekeres theorem: order that must appear
in any large enough structure.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Searches every red/blue coloring of the edges of K_5 and K_6. K_5 has colorings with no single-colored triangle, such as the pentagon and pentagram, but every one of the 32768 colorings of K_6 contains one.">

.. only:: html

  .. image:: /api/gallery/combinatorics/extremal/images/thumb/sphx_glr_plot_01_ramsey_r33_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/extremal/plot_01_ramsey_r33`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Ramsey's theorem: R(3,3) = 6</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Any sequence of (r-1)(s-1)+1 distinct numbers contains an increasing subsequence of length r or a decreasing one of length s. This example finds the longest monotone subsequences of random permutations and shows that their length grows like 2 sqrt(n).">

.. only:: html

  .. image:: /api/gallery/combinatorics/extremal/images/thumb/sphx_glr_plot_02_erdos_szekeres_thumb.png
    :alt:

  :doc:`/api/gallery/combinatorics/extremal/plot_02_erdos_szekeres`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The Erdős-Szekeres theorem: monotone subsequences</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/combinatorics/extremal/plot_01_ramsey_r33
   /api/gallery/combinatorics/extremal/plot_02_erdos_szekeres