Schedule for: 18w5029 - Crossing Numbers: Theory and Applications

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

The organizers will moderate a problem session where the main problems discussed during the week will be outlined and working groups formed.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in the Corbett Hall Lounge for a guided tour of The Banff Centre campus.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

The {\em crossing number} $\Cr(G)$ of a graph $G=(V,E)$ is the smallest number of edge crossings over all drawings of $G$ in the plane. For any $k\ge 1$, the {\em $k$-planar crossing number} of $G$, $\Cr_k(G)$, is defined as the minimum of $\Cr(G_1)+\Cr(G_2)+\ldots+\Cr(G_{k})$ over all graphs $G_1, G_2,\ldots, G_{k}$ with $\cup_{i=1}^{k}G_i=G$. Pach et al. [\emph{Computational Geometry: Theory and Applications} {\bf 68} 2--6, (2018)] showed that for every $k\ge 1$, we have $\Cr_k(G)\le \left(\frac{2}{k^2}-\frac1{k^3}\right)\Cr(G)$ and that this bound does not remain true if we replace the constant $\frac{2}{k^2}-\frac1{k^3}$ by any number smaller than $\frac1{k^2}$. We improve the upper bound to $\frac{1}{k^2}(1+o(1))$ as $k\rightarrow \infty$. For the class of bipartite graphs, we show that the best constant is exactly $\frac{1}{k^2}$ for every $k$. This result needed the existence of a variant of the midrange crossing constant for the class of bipartite graphs. These results extend to the rectilinear variant of the $k$-planar crossing number. This is joint work with {John Asplund}, {\'Eva Czabarka}, {Gregory Clark}, {Garner Cochran}, {Arran Hamm}, {Gwen Spencer}, {Libby Taylor} and {Zhiyu Wang}, originating from a Mathematics Research Communities program.

A buffet dinner is served daily between 5:30pm and 7:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

5-day workshop participants are welcome to use BIRS facilities (BIRS Coffee Lounge, TCPL and Reading Room) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 12 noon.