New lower bounds on crossing numbers of $K_{m,n}$
from permutation modules and semidefinite programming
Joint work with Sven Polak
Daniel Brosch
University of Klagenfurt
February 21, 2024
Crossing numbers of $K_{m,n}$
Crossing numbers of $K_{m,n}$
- Turan, 1940s: Minimum number of crossings of $K_{m,n}$?
- Zarankiewicz's Conjecture, 1956: $$\mathrm{cr}(K_{m,n}) = Z(m,n) := \left\lfloor\frac{(m-1)^2}{4}\right\rfloor \left\lfloor\frac{(n-1)^2}{4}\right\rfloor$$
Still open in most cases, including asymptotically!
Lower bounds for $\mathrm{cr}(K_{m,n})$
- [De Klerk, Maharry, Pasechnik, Richter, Salazar 2006]: Quadratic programming bound $\color{blue}q_m$ and semidefinite programming bound $\color{red}\alpha_m$, computed till $\color{red}\alpha_7$.
Lower bounds for $\mathrm{cr}(K_{m,n})$
- [De Klerk, Maharry, Pasechnik, Richter, Salazar 2006]: Quadratic programming bound $\color{blue}q_m$ and semidefinite programming bound $\color{red}\alpha_m$, computed till $\color{red}\alpha_7$.
- [Dobre, Vera 2015]: Computed a stronger bound on $\color{blue}q_7$.
Lower bounds for $\mathrm{cr}(K_{m,n})$
- [De Klerk, Maharry, Pasechnik, Richter, Salazar 2006]: Quadratic programming bound $\color{blue}q_m$ and semidefinite programming bound $\color{red}\alpha_m$, computed till $\color{red}\alpha_7$.
- [Dobre, Vera 2015]: Computed a stronger bound on $\color{blue}q_7$.
- [De Klerk, Pasechnik, Schrijver 2007]: Computed $\color{red}\alpha_8$, $\color{red}\alpha_9$ using the regular representation.
Lower bounds for $\mathrm{cr}(K_{m,n})$
- [De Klerk, Maharry, Pasechnik, Richter, Salazar 2006]: Quadratic programming bound $\color{blue}q_m$ and semidefinite programming bound $\color{red}\alpha_m$, computed till $\color{red}\alpha_7$.
- [Dobre, Vera 2015]: Computed a stronger bound on $\color{blue}q_7$.
- [De Klerk, Pasechnik, Schrijver 2007]: Computed $\color{red}\alpha_8$, $\color{red}\alpha_9$ using the regular representation.
- [Brosch, Polak 2022]: Computed $\color{red}\alpha_{10}$ using the full symmetry reduction, introduced weaker bound $\beta_m$ and computed it up to $\beta_{13}$.
Lower bounds for $\mathrm{cr}(K_{m,n})$
- [Brosch, Polak 2022]: Computed $\color{red}\alpha_{10}$ using the full symmetry reduction, introduced weaker bound $\beta_m$ and computed it up to $\beta_{13}$.
| $n$ | Old bound | New bound | $Z(n,n)$ |
|---|---|---|---|
| $10$ | $348$ | $388$ | $400$ |
| $11$ | $581$ | $589$ | $625$ |
| $12$ | $846$ | $865$ | $900$ |
| $13$ | $1192$ | $1229$ | $1296$ |
The quadratic programming bound $\color{blue}q_m$
Let $\{1,\ldots,m\}$ and $\{b_1,\ldots,b_n\}$ be the sides of the bipartition of $K_{m,n}$. Given a drawing of $K_{m,n}$, define for each vertex $b_i$:
$$\scriptsize\gamma(b_i) :=\text{ the cyclic order in which edges from $b_i$ go to $\{1,\ldots,m\}$}$$
$$\scriptsize\color{red}\gamma(b_1)=(1 4 5 2 3)$$
$\#$crossings of edges incident with $b_i$ and $b_j$ $\geq$
min. $\#$swaps of adjacent elements of $\gamma(b_i)$ to change $\gamma(b_i)$ into
$\gamma(b_j)^{-1}$.
$\gamma(b_2) = (1 2 3 4 5)$
$\gamma(b_1)^{−1} =
(14523)^{−1} =
(13254)$.
Min. #swaps of adjacent elements is $2$.
Let $Z_m$ be the set of $m$-cycles, and $Q \in \mathbb{Z}^{Z_m\times Z_m}$, where $$\scriptsize Q_{\sigma,\tau} := \text{min. $\#$swaps of adjacent elements to change $\sigma$ into $\tau^{-1}$}$$
$$\scriptsize\displaystyle\begin{align*}
\mathrm{cr}(G) &\geq \min_{\gamma} \sum_{i < j}Q_{\gamma(i),\gamma(j)}\\ & \geq
\tfrac{1}{2}n^2{\color{blue}q_m} - \tfrac{1}{2} n \lfloor \tfrac{1}{4} (m-1)^2\rfloor, \end{align*} $$
where $\scriptsize{\color{blue}q_m} :=\min \left\{x^T Q x \,\, | \,\, x \in \mathbb{R}^{Z_m}_{\geq 0},
\, e^T x=1 \right\} $
The semidefinite programming bound
We relax $$\scriptsize{\color{blue}q_m} :=\min \left\{x^T Q x \,\, | \,\, x \in \mathbb{R}^{Z_m}_{\geq 0}, \, e^T x=1 \right\} $$ to a semidefinite programming problem $$\scriptsize {\color{blue}q_m} \geq {\color{red}\alpha_m} \hspace{-1pt}:=\hspace{-1pt} \min \{\langle X, Q \rangle \, | \, X \in \mathbb{R}^{Z_m \times Z_m}_{\geq 0},\, \langle X, J \rangle =1,\, X \succcurlyeq 0\}.$$
Problem: $|Z_m|=(m-1)!$
Symmetries of the problem
We can relabel the vertices, and mirror the drawing.
Symmetries of the problem
We can relabel the vertices, and mirror the drawing.
Let ${\color{darkorange}G_m} := {\color{darkorange}S_m \times \{+1,-1\}}$ act on $Z_m$ via $${\color{darkorange}(\pi,\varepsilon)}\cdot \sigma := {\color{darkorange}\pi} \sigma^{\color{darkorange}\varepsilon}{\color{darkorange}\pi}^{-1}.$$
Symmetries of the problem
We can relabel the vertices, and mirror the drawing.
Let ${\color{darkorange}G_m} := {\color{darkorange}S_m \times \{+1,-1\}}$ act on $Z_m$ via $${\color{darkorange}(\pi,\varepsilon)}\cdot \sigma := {\color{darkorange}\pi} \sigma^{\color{darkorange}\varepsilon}{\color{darkorange}\pi}^{-1}.$$
Then, for every ${\color{darkorange}g}\in {\color{darkorange}G_m}$: $$({\color{darkorange}g}(Q))_{\sigma,\tau} := Q_{{\color{darkorange}g}(\sigma), {\color{darkorange}g}(\tau)} = Q_{\sigma,\tau}.$$
SDP Symmetry reduction basics
Symmetric solutions
The group $G_m=S_m \times \{+1,-1\}$ acts on $Z_m$ via $${\color{darkorange}(\pi,\varepsilon)}\cdot \sigma := {\color{darkorange}\pi} \sigma^{\color{darkorange}\varepsilon}{\color{darkorange}\pi}^{-1}.$$
This action extends to permute the rows and columns of the positive semidefinite matrix $${\color{darkorange}g}(X):=\left(X_{{\color{darkorange}g}(\sigma), {\color{darkorange}g}(\tau)}\right)_{\sigma, \tau\in Z_m}.$$
As $Q$ has the same symmetries, ${\color{darkorange}g}(X)$ has the same objective value as $X$.
How do we exploit symmetries?
As the feasible set of an SDP is convex, we can average feasible solutions: $$\mathcal{R}(X) := \frac{1}{|{\color{darkorange}G_m}|} \sum_{{\color{darkorange}g}\in {\color{darkorange}G_m}}{\color{darkorange}g}(X)$$ $\mathcal{R}(X)$ is again feasible, with the same objective value as $X$!
Symmetric optimal solutions
Block-diagonalization
is positive semidefinite if and only if
- ${\color{red}A} + {\color{darkorange}B} + {\color{green}C} \geq 0$,
- ${\color{red}A} +\frac{\sqrt{5}-1}{4}{\color{darkorange}B} - \frac{\sqrt{5}+1}{4}{\color{green}C} \geq 0$,
- ${\color{red}A} -\frac{\sqrt{5}+1}{4}{\color{darkorange}B}+\frac{\sqrt{5}-1}{4}{\color{green}C} \geq 0$.
We can find the block-diagonalization using Artin-Wedderburn theory.
Block-diagonalization
The algebra of $G_m$-invariant matrices can be block-diagonalized (by Artin-Wedderburn theory):
Block-diagonalization
[De Klerk, Pasechnik, Schrijver 2007]: Computed $\color{red}\alpha_8$, $\color{red}\alpha_9$ using the regular representation.
Regular representation: One block of size $k\times k$, where $$k=|(Z_m \times Z_m)/G_m|$$ is the number of orbits of pairs.
Block-diagonalization
Regular representation: One block of size $k\times k$, where $$k=|(Z_m \times Z_m)/G_m|$$ is the number of orbits of pairs.
Full symmetry reduction: Many blocks of sizes $m_1, m_2,\ldots$, with $$\sum m_i^2 = k.$$
Block-diagonalization idea
- The vectorspace $\mathbb{C}^{Z_m}$ is a $G_m=S_m\times \{+1,-1\}$-module.
Block-diagonalization idea
- The vectorspace $\mathbb{C}^{Z_m}$ is a $G_m=S_m\times \{+1,-1\}$-module.
- We can decompose the module into copies of irreducible modules $S^{\lambda_i}$: $$\mathbb{C}^{Z_m} \simeq m_1 S^{\lambda_1} \oplus \ldots \oplus m_k S^{\lambda_k} $$
Block-diagonalization idea
- The vectorspace $\mathbb{C}^{Z_m}$ is a $G_m=S_m\times \{+1,-1\}$-module.
- We can decompose the module into copies of irreducible modules $S^{\lambda_i}$: $$\mathbb{C}^{Z_m} \simeq m_1 S^{\lambda_1} \oplus \ldots \oplus m_k S^{\lambda_k} $$
- Choose a basis of $\mathbb{C}^{Z_m}$ according to the decomposition.
Block-diagonalization idea
- The vectorspace $\mathbb{C}^{Z_m}$ is a $G_m=S_m\times \{+1,-1\}$-module.
- We can decompose the module into copies of irreducible modules $S^{\lambda_i}$: $$\mathbb{C}^{Z_m} \simeq m_1 S^{\lambda_1} \oplus \ldots \oplus m_k S^{\lambda_k} $$
- Choose a basis of $\mathbb{C}^{Z_m}$ according to the decomposition.
- Apply a basis transformation to the rows and columns of the SDP, then delete copies of blocks.
Block-diagonalization idea
- We can decompose the module into copies of irreducible modules $S^{\lambda_i}$: $$\mathbb{C}^{Z_m} \simeq m_1 S^{\lambda_1} \oplus \ldots \oplus m_k S^{\lambda_k} $$
Block-diagonalization idea
- We can decompose the module into copies of irreducible modules $S^{\lambda_i}$: $$\mathbb{C}^{Z_m} \simeq m_1 S^{\lambda_1} \oplus \ldots \oplus m_k S^{\lambda_k} $$
The dimension of the module is too high for computational approaches from the literature.
Decomposing $\mathbb{C}^{Z_m}$
-
We first decompose $\mathbb{C}^{Z_m}$ as $S_m$-module:
- The multiplicities $m_i$ are known from the literature!
- But not the explicit decomposition...
Decomposing $\mathbb{C}^{Z_m}$
Idea: Embed $\mathbb{C}^{Z_m}$ into a bigger, well understood module: $$M^{(1^m)} \twoheadrightarrow M^{(1^m)}/_{\mathbb{Z}/m\mathbb{Z}} \simeq \mathbb{C}^{Z_m},$$ where $M^\mu$ denotes a permutation module.
My thesis: Efficient algorithm to explicitely compute the Reynolds operator $\mathcal{R}^\lambda \in \mathbb{Z}^{m_i\times m_i}$ of groups $G$ on the semistandard basis of $\mathrm{hom}(S^\lambda, M^\mu)$, i.e. $$\mathrm{Im}(\mathcal{R}^\lambda)\simeq \mathrm{hom}(S^\lambda, M^\mu/_G).$$
Then we can choose a column-spanning set of basis elements!
Decomposing $\mathbb{C}^{Z_m}$
-
We first decompose $\mathbb{C}^{Z_m}$ as $S_m$-module:
- The multiplicities $m_i$ are known from the literature!
-
But not the explicit decomposition...
Explicit decomposition trough $\mathcal{R}^\lambda$!
- The action of $\{+1,-1\}$ splits each block in two, easy to determine when the $\mathcal{R}^\lambda$ are known.
Decomposing $\mathbb{C}^{Z_m}$
We obtain the full block-diagonalization!
But the relaxation still grows too quickly, we can only compute $\color{red}\alpha_{10}$.
A more efficient relaxation: $\color{green}\beta_m$
- The block coming from the partition $\lambda = (m-2,1,1)$ has size $\lfloor \frac{m-1}{2}\rfloor \in \mathcal{O}(m)$...
- We give an explicit combinatorial block-diagonalization...
- And the bound obtained from ignoring all other blocks is nearly as strong as $\color{red}\alpha_m$!
We solve the dual of $\color{green}\beta_m$: few variables, small matrix block and (exponentially) many linear inequalities.
Computational results
$$\scriptsize\begin{align*} \mathrm{cr}(K_{10,n}) &\geq 4.8705n^2 - 10n&&\geq {\color{gray}4.8345n^2-10n,}\\ \mathrm{cr}(K_{11,n}) &\geq 5.9993n^2-12.5n&&\geq {\color{gray}5.9088n^2 - 12.2222n,}\\ \mathrm{cr}(K_{12,n}) &\geq {7.2557n^2 - 15n}&&\geq {\color{gray}7.0906n^2 - 14.6666n,}\\ \mathrm{cr}(K_{13,n}) &\geq {8.6567n^2-18n}&&\geq {\color{gray}8.3798n^2 -17.3333n.} \end{align*}$$Double counting: Improved bounds for $K_{m,n}$ for $m>13,$ and asymptotic bounds.
Asymptotic bounds
$${\lim_{n \to \infty} \frac{\mathrm{cr}(K_{n,n})}{Z(n,n)} \geq {\frac{8 {\color{red}\alpha_k}}{k(k-1)}}}$$
| $k$ | $\frac{8 {\color{red}\alpha_k}}{k(k-1)}$ | $\frac{8 {\color{green}\beta_k}}{k(k-1)}$ |
|---|---|---|
| $7$ | $0.8303$ | $0.8210$ |
| $8$ | $0.8371 $ | $0.8326$ |
| $9$ | $0.8595$ | $0.8503$ |
| $10$ | $0.8659$ | $0.8610$ |
| $11$ | $0.8726$ | |
| $12$ | $0.8794$ | |
| $13$ | $0.8878$ |
Exact solution for $\beta_m$ possible?
If $m$ is odd, the (numerical) optimal solution of $\beta_m$ is of rank 1. The eigenvectors seem to follow a pattern. Can we guess it?
Summary
- Semidefinite programming gives good lower bounds on $\mathrm{cr}(K_{m,n})$.
- Key contributions: symmetry reduction and new relaxation $\beta_m$ of $\alpha_m$.
- Advantage of approach: only based on $m$-cycles.
- Possible to give optimal solution to $\beta_m$ analytically?
Math. Programming:
doi.org/10.1007/s10107-023-02028-1