New lower bounds on crossing numbers of $K_{m,n}$

from permutation modules and semidefinite programming


Daniel Brosch (University of Klagenfurt)

(Based on joint work with Sven Polak)

April 14, 2023

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)$$
Lemma [Kleitman, 1970; Woodall, 1993]

$\#$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)!$

Symmetry reduction

Let $G_m := S_m \times \{+1,-1\}$ act on $Z_m$ via $$(\pi,\varepsilon)\cdot \sigma := \pi \sigma^\varepsilon\pi^{-1}.$$

Symmetry reduction

Let $G_m := S_m \times \{+1,-1\}$ act on $Z_m$ via $$(\pi,\varepsilon)\cdot \sigma := \pi \sigma^\varepsilon\pi^{-1}.$$


Then, for every $g\in G_m$: $$(g(Q))_{\sigma,\tau} = Q_{g(\sigma), g(\tau)} = Q_{\sigma,\tau}.$$

Symmetry reduction

Let $G_m := S_m \times \{+1,-1\}$ act on $Z_m$ via $$(\pi,\varepsilon)\cdot \sigma := \pi \sigma^\varepsilon\pi^{-1}.$$

Then, for every $g\in G_m$: $$(g(Q))_{\sigma,\tau} = Q_{g(\sigma), g(\tau)} = Q_{\sigma,\tau}.$$

Main idea: If $X$ is feasible for $\color{red}\alpha_m$, then so is $g(X)$. By convexity we can average an optimal solution to obtain an invariant optimal solution.

Symmetry reduction

Main idea: If $X$ is feasible for $\color{red}\alpha_m$, then so is $g(X)$. By convexity we can average an optimal solution to obtain an invariant optimal solution.


$$\scriptsize \begin{align*} {\color{red}\alpha_m} \hspace{-1pt}=\hspace{-1pt} \min\enspace &\langle X, Q \rangle \\ \text{s.t. }&X \in \mathbb{R}^{Z_m \times Z_m}_{\geq 0},\\ &\langle X, J \rangle =1,\\ &X \succcurlyeq 0,\\ & {\color{red}g(X) = X \quad \text{for all }g\in G_m}. \end{align*}$$

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

Lemma [de Klerk, Maharry, Pasechnik, Richter, Salazar 2006]

$${\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?


arXiv:2206.02755