{
"cells": [
{
"cell_type": "markdown",
"id": "d0c9c1d0-ee11-48e5-9415-90d10b24d1fb",
"metadata": {},
"source": [
"# Polytope analysis"
]
},
{
"cell_type": "markdown",
"id": "9103d416-8dbc-4339-9db2-8320d0b3b8a0",
"metadata": {},
"source": [
"## Computing kernel basis"
]
},
{
"cell_type": "markdown",
"id": "d514cc11-d5e6-466e-b4ac-834e6d0aab0a",
"metadata": {},
"source": [
"The graph edge kernel describes the degree of freedom of the feasible matching rates, if any."
]
},
{
"cell_type": "markdown",
"id": "c2e029f0-82eb-49b7-a6b0-04b6582aa3e7",
"metadata": {},
"source": [
"[Stochastic Matching](https://balouf.github.io/stochastic_matching/index.html) provides tools to compute and display the edge kernel."
]
},
{
"cell_type": "markdown",
"id": "fe990b02-f922-47a1-acf9-70c3c1a41d4d",
"metadata": {},
"source": [
"### Examples of 1-D kernels"
]
},
{
"cell_type": "markdown",
"id": "0ac8f1c0-f940-46af-95cf-8203ed1e442e",
"metadata": {},
"source": [
"#### Diamond"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "6e547af1-0303-4ba3-bebc-e5150801c628",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:58.043914Z",
"iopub.status.busy": "2025-09-26T18:31:58.042915Z",
"iopub.status.idle": "2025-09-26T18:31:59.275258Z",
"shell.execute_reply": "2025-09-26T18:31:59.275258Z",
"shell.execute_reply.started": "2025-09-26T18:31:58.043914Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"Kernels of a graph with 4 nodes and 5 edges.\n",
"Node dimension is 0.\n",
"Edge dimension is 1\n",
"Type: Surjective-only\n",
"Node kernel:\n",
"[]\n",
"Edge kernel:\n",
"[[ 1 -1 0 -1 1]]"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import stochastic_matching as sm\n",
"diamond = sm.CycleChain(names=[str(i) for i in [1, 2, 3, 4]])\n",
"diamond.kernel"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "d3eccc78-5605-4e7f-9e0d-6ab22b0a3385",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.276700Z",
"iopub.status.busy": "2025-09-26T18:31:59.275258Z",
"iopub.status.idle": "2025-09-26T18:31:59.279707Z",
"shell.execute_reply": "2025-09-26T18:31:59.279707Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.276700Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"diamond.show_kernel(disp_rates=False)"
]
},
{
"cell_type": "markdown",
"id": "0b2585eb-72d2-4ce4-97af-2d138b00a3f0",
"metadata": {},
"source": [
":::note\n",
"The edge without value does not belong to the support of the kernel, i.e. for a given problem $(G, \\lambda)$, its matching rate is the same for all stable policies.\n",
":::"
]
},
{
"cell_type": "markdown",
"id": "27409ee2-36a2-4ab7-99c3-b5fc65ae3bb3",
"metadata": {},
"source": [
"#### Unbalanced Kayak Paddle"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "35bf3300-45c3-4fae-ab6c-b9da403e6231",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.280875Z",
"iopub.status.busy": "2025-09-26T18:31:59.279707Z",
"iopub.status.idle": "2025-09-26T18:31:59.291732Z",
"shell.execute_reply": "2025-09-26T18:31:59.291732Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.280875Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"Kernels of a graph with 9 nodes and 10 edges.\n",
"Node dimension is 0.\n",
"Edge dimension is 1\n",
"Type: Surjective-only\n",
"Node kernel:\n",
"[]\n",
"Edge kernel:\n",
"[[-1 1 1 -2 2 -1 -1 1 -1 1]]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"kayak = sm.KayakPaddle(k=3,l=2,m=5, names=[str(i+1) for i in range(9)])\n",
"kayak.kernel"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "4c18077d-f1ac-474f-b865-d301b5477cef",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.292743Z",
"iopub.status.busy": "2025-09-26T18:31:59.291732Z",
"iopub.status.idle": "2025-09-26T18:31:59.296199Z",
"shell.execute_reply": "2025-09-26T18:31:59.296199Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.292743Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"kayak.show_kernel(disp_rates=False)"
]
},
{
"cell_type": "markdown",
"id": "a8b2ed37-5816-4ea1-911e-a8d37b1bc988",
"metadata": {},
"source": [
"#### Hypergraphs"
]
},
{
"cell_type": "markdown",
"id": "708a3672-d806-4922-8e94-4239b7094a8a",
"metadata": {},
"source": [
"The simplest 1-D hypergraph is two connected nodes with abandonment. The degree of liberty is then: match items or not."
]
},
{
"cell_type": "markdown",
"id": "ab31838d-6802-439c-b07a-684f67a986b7",
"metadata": {},
"source": [
":::note\n",
"For hypergraphs, the kernel algorithm is optimized in a generic way, not using the edge-cycle algorithm, which only works on simple graphs.\n",
":::"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "302c851a-ee80-40e9-96a9-ed9497fbfd50",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.297544Z",
"iopub.status.busy": "2025-09-26T18:31:59.296199Z",
"iopub.status.idle": "2025-09-26T18:31:59.305882Z",
"shell.execute_reply": "2025-09-26T18:31:59.304305Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.297544Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"Kernels of a graph with 2 nodes and 3 edges.\n",
"Node dimension is 0.\n",
"Edge dimension is 1\n",
"Type: Surjective-only\n",
"Node kernel:\n",
"[]\n",
"Edge kernel:\n",
"[[-0.57735027 -0.57735027 0.57735027]]"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"two_nodes = sm.Model(incidence=[[1, 0, 1],[0, 1, 1]], names=[\"1\", \"2\"])\n",
"two_nodes.kernel"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "f2b61b3a-e1e9-4dc8-a544-84cde240d566",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.307300Z",
"iopub.status.busy": "2025-09-26T18:31:59.307300Z",
"iopub.status.idle": "2025-09-26T18:31:59.312902Z",
"shell.execute_reply": "2025-09-26T18:31:59.312902Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.307300Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"two_nodes.show_kernel(disp_rates=False)"
]
},
{
"cell_type": "markdown",
"id": "4ea019d6-c48d-4292-8ea7-4968862fe7a6",
"metadata": {},
"source": [
":::note\n",
"For hypergraphs, we use the standard representation as a bipartite graph with nodes on what side and hyperedges on the other side. However, by default, we do not enforce a physical separation with actual left and right parts. This is a deliberate choice as we find the hypergraphs easier to read without a physical separation, especially if there are close to a simple graph. However, the option exists. You can for example compare the following hypergraph, which is a regular two-way triangle with one additional multi-way match involving 6 items (1 of type $A$, 2 of type $B$, 3 of type $C$), in both representations:\n",
":::"
]
},
{
"cell_type": "code",
"execution_count": 29,
"id": "ed1f357e-b988-4f9f-b685-a7316dd0e77f",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:33:43.694188Z",
"iopub.status.busy": "2025-09-26T18:33:43.694188Z",
"iopub.status.idle": "2025-09-26T18:33:43.704354Z",
"shell.execute_reply": "2025-09-26T18:33:43.703349Z",
"shell.execute_reply.started": "2025-09-26T18:33:43.694188Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"import numpy as np\n",
"hypertriangle = sm.Model(incidence=np.hstack([sm.Cycle(n=3).incidence, np.array([[1, 2, 3]]).T]), names=\"alpha\")\n",
"hypertriangle.show_kernel(disp_rates=False)"
]
},
{
"cell_type": "code",
"execution_count": 30,
"id": "1493bd37-bce3-454e-a6d2-083b112a72bf",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:33:45.734675Z",
"iopub.status.busy": "2025-09-26T18:33:45.733675Z",
"iopub.status.idle": "2025-09-26T18:33:45.739414Z",
"shell.execute_reply": "2025-09-26T18:33:45.739414Z",
"shell.execute_reply.started": "2025-09-26T18:33:45.734675Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"hypertriangle.show_kernel(disp_rates=False, bipartite=True)"
]
},
{
"cell_type": "markdown",
"id": "eba32550-267f-4744-a48b-849bb04c7231",
"metadata": {},
"source": [
"### Examples of 2-D kernels"
]
},
{
"cell_type": "markdown",
"id": "dd795d84-a04d-4c6b-aa41-097863a9d586",
"metadata": {},
"source": [
"#### Co-Domino"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "ee091868-d9a0-4e57-b8bf-ec1c88dbb700",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.328570Z",
"iopub.status.busy": "2025-09-26T18:31:59.328570Z",
"iopub.status.idle": "2025-09-26T18:31:59.333546Z",
"shell.execute_reply": "2025-09-26T18:31:59.333546Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.328570Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"Kernels of a graph with 6 nodes and 8 edges.\n",
"Node dimension is 0.\n",
"Edge dimension is 2\n",
"Type: Surjective-only\n",
"Node kernel:\n",
"[]\n",
"Edge kernel:\n",
"[[ 0 0 1 -1 -1 1 0 0]\n",
" [ 1 -1 0 -1 1 0 -1 1]]"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"codomino = sm.Codomino(names=[\"1\", \"2\", \"6\", \"5\", \"3\", \"4\"])\n",
"codomino.kernel"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "35b0c7bb-cf1e-454c-a176-6012fad1ed29",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.334557Z",
"iopub.status.busy": "2025-09-26T18:31:59.334557Z",
"iopub.status.idle": "2025-09-26T18:31:59.339381Z",
"shell.execute_reply": "2025-09-26T18:31:59.339381Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.334557Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"codomino.show_kernel(disp_rates=False)"
]
},
{
"cell_type": "markdown",
"id": "7a7585ba-8703-4a92-a3e7-145fc44deb55",
"metadata": {},
"source": [
"For multi-dimensional kernels, the possible basis are not unique. However, one can hint at a specific basis by specifying *seed* edges (cf paper)."
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "8cf2c938-4ff9-4c0b-ab4c-f72b00771b02",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.339381Z",
"iopub.status.busy": "2025-09-26T18:31:59.339381Z",
"iopub.status.idle": "2025-09-26T18:31:59.345697Z",
"shell.execute_reply": "2025-09-26T18:31:59.345697Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.339381Z"
}
},
"outputs": [
{
"data": {
"text/plain": [
"Kernels of a graph with 6 nodes and 8 edges.\n",
"Node dimension is 0.\n",
"Edge dimension is 2\n",
"Type: Surjective-only\n",
"Node kernel:\n",
"[]\n",
"Edge kernel:\n",
"[[ 1 -1 -1 0 2 -1 -1 1]\n",
" [ 0 0 -1 1 1 -1 0 0]]"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"codomino.seeds = [0, 3]\n",
"codomino.kernel"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "15115502-698b-4f68-b919-cd824f6fa82e",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.347128Z",
"iopub.status.busy": "2025-09-26T18:31:59.345697Z",
"iopub.status.idle": "2025-09-26T18:31:59.352296Z",
"shell.execute_reply": "2025-09-26T18:31:59.352296Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.347128Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"codomino.show_kernel(disp_rates=False)"
]
},
{
"cell_type": "markdown",
"id": "4b8c0658-4baa-4900-96b9-13dc22325e04",
"metadata": {},
"source": [
"#### Triamond"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "2ececa72-bd4b-46d1-96ee-4473e8ba50b7",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.353743Z",
"iopub.status.busy": "2025-09-26T18:31:59.352296Z",
"iopub.status.idle": "2025-09-26T18:31:59.359073Z",
"shell.execute_reply": "2025-09-26T18:31:59.359073Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.353743Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"triamond = sm.CycleChain(c=3, names=[str(i) for i in [1, 5, 2, 4, 3]])\n",
"triamond.seeds = [1, 3]\n",
"triamond.show_kernel(disp_rates=False)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "205b5e0e-4880-4f86-8fbd-f746e307c46e",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.360510Z",
"iopub.status.busy": "2025-09-26T18:31:59.359073Z",
"iopub.status.idle": "2025-09-26T18:31:59.364084Z",
"shell.execute_reply": "2025-09-26T18:31:59.364084Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.360510Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"triamond.seeds = [4, 2]\n",
"triamond.show_kernel(disp_rates=False)"
]
},
{
"cell_type": "markdown",
"id": "32f7d9b9-e974-4814-85c6-460af914140d",
"metadata": {},
"source": [
"## Vertices"
]
},
{
"cell_type": "markdown",
"id": "57d8c934-da80-4b54-9229-a65091a20234",
"metadata": {},
"source": [
"### Co-domino variations"
]
},
{
"cell_type": "markdown",
"id": "c16fa30a-f2c3-472d-bd36-665d59eae689",
"metadata": {},
"source": [
"Just by changing the arrival rates, one can change a lot the properties of the polytope of feasible matching rates. Using the codomino graph (one of the smallest possible simple graph with a 2-D kernel), one can observe how different the polytope can be."
]
},
{
"cell_type": "markdown",
"id": "04ecb5d0-6e62-451a-aec5-fc992028378e",
"metadata": {},
"source": [
"#### Mix of injective-only and bijective vertices"
]
},
{
"cell_type": "markdown",
"id": "8d6b922f-19f6-4552-a27f-e3d94aacadc8",
"metadata": {},
"source": [
"By default, arrival rates are proportional to node degrees. This often yields to many injective-only vertices, as shown by the codomino."
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "32c660fa-e74e-4151-b11b-5f6bda3e7878",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.364084Z",
"iopub.status.busy": "2025-09-26T18:31:59.364084Z",
"iopub.status.idle": "2025-09-26T18:31:59.371872Z",
"shell.execute_reply": "2025-09-26T18:31:59.371872Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.364084Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"codomino.seeds = [1, 2] # We use the seeds to select a kernel basis\n",
"codomino.show_kernel(disp_flow=True, disp_rates=False)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "085c2c70-a3a8-4b14-a8c5-c1cfc7d2d671",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.373033Z",
"iopub.status.busy": "2025-09-26T18:31:59.371872Z",
"iopub.status.idle": "2025-09-26T18:31:59.387524Z",
"shell.execute_reply": "2025-09-26T18:31:59.387524Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.373033Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [2. 0. 0. 1. 3. 0. 0. 2.] (edge) / [-1. -1.] (kernel) is injective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [2. 0. 1. 0. 2. 1. 0. 2.] (edge) / [-1. 0.] (kernel) is injective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [1. 1. 2. 0. 0. 2. 1. 1.] (edge) / [0. 1.] (kernel) is bijective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [0. 2. 0. 3. 1. 0. 2. 0.] (edge) / [ 1. -1.] (kernel) is injective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [0. 2. 1. 2. 0. 1. 2. 0.] (edge) / [1. 0.] (kernel) is injective.\n"
]
}
],
"source": [
"def show_vertices(model):\n",
" for i, v in enumerate(model.vertices):\n",
" model.show_vertex(i, disp_rates=False)\n",
" \n",
" print(f\"Vertex of coordinates {str(v['edge_coordinates'])} (edge) / {v['kernel_coordinates']} (kernel) is {'bijective' if v['bijective'] else 'injective'}.\")\n",
"show_vertices(codomino)"
]
},
{
"cell_type": "markdown",
"id": "5ca6756e-2359-4c7a-8998-3b9c5c70be1d",
"metadata": {},
"source": [
"#### 3 injective-only vertices"
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "057a2f7c-dee2-4ddc-8d0c-1debd3dcf56f",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.387524Z",
"iopub.status.busy": "2025-09-26T18:31:59.387524Z",
"iopub.status.idle": "2025-09-26T18:31:59.392533Z",
"shell.execute_reply": "2025-09-26T18:31:59.392533Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.387524Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"codomino.rates = [2, 4, 2, 2, 4, 2]\n",
"# We shift the base_flow so coordinates are simpler\n",
"codomino.base_flow = codomino.kernel_to_edge([1/3, 0])\n",
"codomino.show_kernel(disp_flow=True, disp_rates=False)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"id": "e725c162-40c5-4aeb-9ada-44d1ffbdb484",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.393665Z",
"iopub.status.busy": "2025-09-26T18:31:59.392533Z",
"iopub.status.idle": "2025-09-26T18:31:59.404135Z",
"shell.execute_reply": "2025-09-26T18:31:59.404135Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.393665Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [2. 0. 2. 0. 0. 2. 0. 2.] (edge) / [-1. 1.] (kernel) is injective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [2. 0. 0. 2. 2. 0. 0. 2.] (edge) / [-1. -1.] (kernel) is injective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [0. 2. 0. 4. 0. 0. 2. 0.] (edge) / [ 1. -1.] (kernel) is injective.\n"
]
}
],
"source": [
"show_vertices(codomino)"
]
},
{
"cell_type": "markdown",
"id": "0ba0fe9c-2071-4750-a9bb-121214802d04",
"metadata": {},
"source": [
"#### 3 bijective vertices"
]
},
{
"cell_type": "code",
"execution_count": 19,
"id": "64bb169a-6d54-4746-9f94-9f64502c5db7",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.405142Z",
"iopub.status.busy": "2025-09-26T18:31:59.404135Z",
"iopub.status.idle": "2025-09-26T18:31:59.408453Z",
"shell.execute_reply": "2025-09-26T18:31:59.408453Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.405142Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"codomino.rates = [4, 4, 4, 3, 3, 4]\n",
"codomino.base_flow = codomino.kernel_to_edge([0, -1/4])\n",
"codomino.show_kernel(disp_flow=True, disp_rates=False)"
]
},
{
"cell_type": "code",
"execution_count": 20,
"id": "8f28a307-5724-4d35-89ab-b9824cd9a44a",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.408453Z",
"iopub.status.busy": "2025-09-26T18:31:59.408453Z",
"iopub.status.idle": "2025-09-26T18:31:59.420105Z",
"shell.execute_reply": "2025-09-26T18:31:59.420105Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.408453Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [3. 1. 1. 0. 2. 0. 1. 3.] (edge) / [-1. 0.] (kernel) is bijective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [2. 2. 2. 0. 0. 1. 2. 2.] (edge) / [0. 1.] (kernel) is bijective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [1. 3. 1. 2. 0. 0. 3. 1.] (edge) / [1. 0.] (kernel) is bijective.\n"
]
}
],
"source": [
"show_vertices(codomino)"
]
},
{
"cell_type": "markdown",
"id": "529c59ff-a662-428d-baae-eb099263b6f8",
"metadata": {},
"source": [
"#### 5 bijective vertices"
]
},
{
"cell_type": "code",
"execution_count": 21,
"id": "1d7cdb89-51da-4eca-b413-4c175cf0d2fa",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.422206Z",
"iopub.status.busy": "2025-09-26T18:31:59.421199Z",
"iopub.status.idle": "2025-09-26T18:31:59.425474Z",
"shell.execute_reply": "2025-09-26T18:31:59.425474Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.422206Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"codomino.rates = [4, 5, 5, 3, 3, 2]\n",
"codomino.base_flow = codomino.kernel_to_edge([0, 1/4])\n",
"codomino.show_kernel(disp_rates=False, disp_flow=True)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"id": "9556dfc9-1713-4e91-9c04-f11e58809ed2",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.426485Z",
"iopub.status.busy": "2025-09-26T18:31:59.426485Z",
"iopub.status.idle": "2025-09-26T18:31:59.441686Z",
"shell.execute_reply": "2025-09-26T18:31:59.441686Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.426485Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [3. 1. 1. 1. 3. 0. 0. 2.] (edge) / [-1. -1.] (kernel) is bijective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [3. 1. 2. 0. 2. 1. 0. 2.] (edge) / [-1. 0.] (kernel) is bijective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [2. 2. 3. 0. 0. 2. 1. 1.] (edge) / [0. 1.] (kernel) is bijective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [1. 3. 2. 2. 0. 1. 2. 0.] (edge) / [1. 0.] (kernel) is bijective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [1. 3. 1. 3. 1. 0. 2. 0.] (edge) / [ 1. -1.] (kernel) is bijective.\n"
]
}
],
"source": [
"show_vertices(codomino)"
]
},
{
"cell_type": "markdown",
"id": "ec014df5-6cee-42c1-8722-d236f18947d0",
"metadata": {},
"source": [
"### Pyramid polytope"
]
},
{
"cell_type": "markdown",
"id": "428cb685-4547-4c3d-8561-c8a4da268da1",
"metadata": {},
"source": [
"Starting from 3-D kernels, it is possible to have an injective-only vertex even if all tight edges are irredundant. One of the simple example is the Egyptian pyramid, where 4 distinct planes intersect at one point (the top of the pyramid). The following model was specifically designed so that its polytope is pyramid-shaped."
]
},
{
"cell_type": "code",
"execution_count": 23,
"id": "87994b3d-be9b-4c27-9f70-173c39537f3a",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.441686Z",
"iopub.status.busy": "2025-09-26T18:31:59.441686Z",
"iopub.status.idle": "2025-09-26T18:31:59.447579Z",
"shell.execute_reply": "2025-09-26T18:31:59.447579Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.441686Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"pyramid = sm.Pyramid(\n",
" rates=[4, 3, 3, 3, 6, 6, 3, 4, 4, 4],\n",
" names=[\"9\", \"2\", \"1\", \"8\", \"7\", \"3\", \"4\", \"5\", \"6\", \"10\"],\n",
")\n",
"pyramid.seeds = [0, 12, 2]\n",
"pyramid.base_flow = pyramid.kernel_to_edge([1 / 6, 1 / 6, 1 / 6])\n",
"pyramid.show_kernel(disp_flow=True, disp_rates=False)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"id": "832bca27-9baf-4a43-a7e3-194f60f29a54",
"metadata": {
"execution": {
"iopub.execute_input": "2025-09-26T18:31:59.447579Z",
"iopub.status.busy": "2025-09-26T18:31:59.447579Z",
"iopub.status.idle": "2025-09-26T18:31:59.462590Z",
"shell.execute_reply": "2025-09-26T18:31:59.462590Z",
"shell.execute_reply.started": "2025-09-26T18:31:59.447579Z"
}
},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [1. 3. 0. 2. 0. 3. 3. 0. 1. 2. 1. 1. 3.] (edge) / [-1. 1. 0.] (kernel) is bijective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [1. 3. 0. 2. 0. 3. 1. 2. 3. 0. 1. 3. 1.] (edge) / [-1. -1. 0.] (kernel) is bijective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [2. 2. 1. 0. 0. 3. 3. 0. 3. 0. 2. 2. 2.] (edge) / [0. 0. 1.] (kernel) is injective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [3. 1. 0. 0. 2. 1. 3. 2. 3. 0. 1. 3. 1.] (edge) / [ 1. -1. 0.] (kernel) is bijective.\n"
]
},
{
"data": {
"text/html": [
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Vertex of coordinates [3. 1. 0. 0. 2. 1. 5. 0. 1. 2. 1. 1. 3.] (edge) / [1. 1. 0.] (kernel) is bijective.\n"
]
}
],
"source": [
"show_vertices(pyramid)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.8"
}
},
"nbformat": 4,
"nbformat_minor": 5
}