$$\require{color}$$ $$\definecolor{darkorange}{rgb}{0.75, 0.40, 0}$$

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

June 6, 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)$$
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)!$

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

If $X$ is positive semidefinite, then ${\color{darkorange}g}(X)$ is as well!
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

If $X^*$ is an optimal solution, then so is $\mathcal{R}(X^*)$. This solution is invariant under actions of ${\color{darkorange}G_m}$: $${\color{darkorange}g}(\mathcal{R}(X^*)) = \mathcal{R}(X^*). $$ We can restrict the SDP to optimize only over invariant matrices: $$\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*}$$ Example: In the case of ${\color{darkorange}G}=D_{10}=C_5\times Z_2$ we can restrict $X$ to have the pattern $$\begin{pmatrix} {\color{red}A} & {\color{darkorange}B} & {\color{green}C} & {\color{green}C} & {\color{darkorange}B}\\ {\color{darkorange}B} & {\color{red}A} & {\color{darkorange}B} & {\color{green}C} & {\color{green}C}\\ {\color{green}C} & {\color{darkorange}B} & {\color{red}A} & {\color{darkorange}B} & {\color{green}C}\\ {\color{green}C} & {\color{green}C} & {\color{darkorange}B} & {\color{red}A} & {\color{darkorange}B} \\ {\color{darkorange}B} & {\color{green}C} & {\color{green}C} & {\color{darkorange}B} & {\color{red}A}\\ \end{pmatrix}$$

Block-diagonalization

$$\small\begin{pmatrix} {\color{red}A} & {\color{darkorange}B} & {\color{green}C} & {\color{green}C} & {\color{darkorange}B}\\ {\color{darkorange}B} & {\color{red}A} & {\color{darkorange}B} & {\color{green}C} & {\color{green}C}\\ {\color{green}C} & {\color{darkorange}B} & {\color{red}A} & {\color{darkorange}B} & {\color{green}C}\\ {\color{green}C} & {\color{green}C} & {\color{darkorange}B} & {\color{red}A} & {\color{darkorange}B} \\ {\color{darkorange}B} & {\color{green}C} & {\color{green}C} & {\color{darkorange}B} & {\color{red}A}\\ \end{pmatrix} $$

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$.
In general we may still get multiple bigger blocks

but the sum of the block sizes is often significantly smaller!

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

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$

[Balogh, Lidicky, Norin, Pfender, Salazar, Spiro, September '23]: Asymptotic bound 0.9118

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