.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/topology/fixed_points/plot_04_sperner_lemma.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_topology_fixed_points_plot_04_sperner_lemma.py>`
        to download the full example code or to run this example in your browser via JupyterLite.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_topology_fixed_points_plot_04_sperner_lemma.py:


Sperner's lemma (1928)
======================

Subdivide a triangle and label each vertex 0, 1 or 2, with the corners
labelled 0, 1, 2 and each side vertex labelled like one of its side's
endpoints (interior labels are free). Emanuel Sperner proved that an
*odd* number of small triangles carry all three labels. Picture labels
0-1 edges as doors: one enters from the bottom side, and following
doors from room to room can only stop in a fully labelled room.

.. GENERATED FROM PYTHON SOURCE LINES 14-23

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.topology import fully_labeled_triangles, random_sperner_labeling, triangle_grid

    grid = triangle_grid(12)
    counts = [len(fully_labeled_triangles(grid, random_sperner_labeling(grid, seed=s))) for s in range(2000)]
    print("fully labelled triangles over 2000 random labellings: all odd?", all(c % 2 == 1 for c in counts))





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    fully labelled triangles over 2000 random labellings: all odd? True




.. GENERATED FROM PYTHON SOURCE LINES 24-26

One labelling, its doors, and its fully labelled triangles
----------------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 26-54

.. code-block:: Python


    labels = random_sperner_labeling(grid, seed=7)
    full = fully_labeled_triangles(grid, labels)
    xy = grid.cartesian
    fig, axes = plt.subplots(1, 2, figsize=(12, 5.5), width_ratios=(1.2, 1))
    ax = axes[0]
    ax.triplot(*xy.T, grid.triangles, color="0.75", lw=0.6)
    for tri in grid.triangles[full]:
        ax.add_patch(plt.Polygon(xy[tri], color="gold", ec="k", zorder=2))
    for tri in grid.triangles:
        for a, b in ((0, 1), (1, 2), (0, 2)):
            if {labels[tri[a]], labels[tri[b]]} == {0, 1}:
                ax.plot(*xy[[tri[a], tri[b]]].T, color="tab:purple", lw=2.5, zorder=1)
    for k, color in enumerate(("tab:red", "tab:green", "tab:blue")):
        ax.scatter(*xy[labels == k].T, s=25, color=color, zorder=3, label=f"label {k}")
    ax.plot([], [], color="tab:purple", lw=2.5, label="0-1 door")
    ax.set_aspect("equal")
    ax.axis("off")
    ax.legend(loc="upper right", fontsize=8)
    ax.set_title(f"{len(full)} fully labelled triangles (gold)")

    ax = axes[1]
    values, freq = np.unique(counts, return_counts=True)
    ax.bar(values, freq, color="tab:orange")
    ax.set_xlabel("number of fully labelled triangles")
    ax.set_ylabel("labellings")
    ax.set_title("always odd")
    fig.suptitle("Sperner (1928)")



.. image-sg:: /api/gallery/topology/fixed_points/images/sphx_glr_plot_04_sperner_lemma_001.png
   :alt: Sperner (1928), 35 fully labelled triangles (gold), always odd
   :srcset: /api/gallery/topology/fixed_points/images/sphx_glr_plot_04_sperner_lemma_001.png
   :class: sphx-glr-single-img


.. rst-class:: sphx-glr-script-out

 .. code-block:: none


    Text(0.5, 0.98, 'Sperner (1928)')




.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.572 seconds)


.. _sphx_glr_download_api_gallery_topology_fixed_points_plot_04_sperner_lemma.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: lite-badge

      .. image:: images/jupyterlite_badge_logo.svg
        :target: ../../../../lite/lab/index.html?path=api/gallery/topology/fixed_points/plot_04_sperner_lemma.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_04_sperner_lemma.ipynb <plot_04_sperner_lemma.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_04_sperner_lemma.py <plot_04_sperner_lemma.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_04_sperner_lemma.zip <plot_04_sperner_lemma.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_