Georgia Institute of Technology College of Sciences

A class of graphs is said to be $\chi$-bounded with binding function $f$ if for every such graph $G$, it satisfies $\chi(G) \leq f(\omega(G)$, and polynomially $\chi$-bounded if $f$ is a polynomial. It was conjectured that chair-free graphs are perfectly divisible, and hence admit a quadratic $\chi$-binding function. In addition to confirming that chair-free graphs admit a quadratic $\chi$-binding function, we will extend the result by demonstrating that $t$-broom free graphs are polynomially $\chi$-bounded for any $t$ with binding function $f(\omega) = O(\omega^{t+1})$. A class of graphs is said to satisfy the Vizing bound if it admits the $\chi$-binding function $f(\omega) = \omega + 1$. It was conjectured that (fork, $K_3$)-free graphs would be 3-colorable, where fork is the graph obtained from $K_{1, 4}$ by subdividing two edges. This would also imply that (paw, fork)-free graphs satisfy the Vizing bound. We will prove this conjecture through a series of lemmas that constrain the structure of any minimal counterexample.

The Meeting on Applied Algebraic Geometry (MAAG 2023) is a regional gathering which attracts participants primarily from the South-East of the United States. Previous meetings took place at Georgia Tech in 2015, 2018, and 2019, and at Clemson in 2016.

For more information and to register, please visit https://sites.google.com/view/maag-2023. The registration is free until February 28th, 2023, and the registration fee will become $50 after that. 

MAAG will be followed by a Macaulay2 Day on April 16.

Organizers: Abeer Al Ahmadieh, Greg Blekherman, Anton Leykin, and Josephine Yu.

In this talk, we use semidefinite programming and representation theory to compute new lower bounds on the crossing number of the complete bipartite graph $K_{m,n}$, extending a method from de Klerk et al. [SIAM J. Discrete Math. 20 (2006), 189--202] and the subsequent reduction by De Klerk, Pasechnik and Schrijver [Math. Prog. Ser. A and B, 109 (2007) 613--624].
 
We exploit the full symmetry of the problem by developing a block-diagonalization of the underlying matrix algebra and use it to improve bounds on several concrete instances. Our results imply that $\mathrm{cr}(K_{10,n}) \geq  4.87057 n^2 - 10n$, $\mathrm{cr}(K_{11,n}) \geq 5.99939 n^2-12.5n$, $\mathrm{cr}(K_{12,n}) \geq 7.25579 n^2 - 15n$, $\mathrm{cr}(K_{13,n}) \geq 8.65675 n^2-18n$ for all~$n$. The latter three bounds are computed using a new relaxation of the original semidefinite programming bound, by only requiring one small matrix block to be positive semidefinite. Our lower bound on $K_{13,n}$ implies that for each fixed $m \geq 13$, $\lim_{n \to \infty} \text{cr}(K_{m,n})/Z(m,n) \geq 0.8878 m/(m-1)$. Here $Z(m,n)$ is the Zarankiewicz number: the conjectured crossing number of $K_{m,n}$.
 
This talk is based on joint work with Sven Polak.