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)

December 1, 2022

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}$.

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.

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} $$

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}$

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

Double counting: Improved bounds for $K_{m,n}$ for $m>13$, and asymptotic bounds.

Asymptotic bounds

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

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 optimum solution to $\beta_m$ analytically?

arXiv:2206.02755