Susanne Fishel, Arizona State University.
Title: Maximal length chains in lattices from graph associahedra
Abstract: Tubing posets are orientations of the 1-skeleton of graph associahedra. For the complete graph on $n$ vertices, the poset is the weak order on the symmetric group. When the graph is the path on n vertices, the poset is the Tamari lattice. We consider tubing posets of a family of graphs which interpolates between the complete and the path graphs. We discuss enumeration of the maximal length chains of the lattices corresponding to this graph family, first in terms of standard Young tableaux, then using quasisymmetric functions. I will also discuss recent results for more general graphs. We assume no prior knowledge of any of the topics in the talk. This is joint work with Samantha Dahlberg and with Manuel Concha, Hsin-Chieh Liao, and Andrew Reimer-Berg.
Andres R. Vindas Melendez, Harvey Mudd College.
Title: q-Chromatic polynomials
Abstract: We introduce and study a $q$-version of the chromatic polynomial of a given graph $G=(V,E)$, namely, \[ \chi_G^\lambda(q,n) \ :=\sum_{\substack{\text{proper colorings}\\ c\,:\,V\to[n]}} q^{ \sum_{ v \in V } \lambda_v c(v) }, \] where $\lambda \in \mathbb{Z}^V$ is a fixed linear form. Via work of Chapoton (2016) on $q$-Ehrhart polynomials, $\chi_G^\lambda(q,n)$ turns out to be a polynomial in the $q$-integer $[n]_q$, with coefficients that are rational functions in $q$. Additionally, we prove structural results for $\chi_G^\lambda(q,n)$ and exhibit connections to neighboring concepts, e.g., chromatic symmetric functions and the arithmetic of order polytopes. We offer a strengthened version of Stanley's conjecture that the chromatic symmetric function distinguishes trees, which leads to an analogue of $P$-partitions for graphs. This is joint work with Esme Bajo (San Diego Miramar College) and Matthias Beck (San Francisco State).
Alejandro H. Morales , Université du Québec à Montréal
Title: Skew, luck and magic of parking functions via Pitman-Stanley polytopes
Abstract:
Zi-Xia Song, University of Central Florida
Title: Dominating Hadwiger’s Conjecture
Abstract: Adominating Kt minor in a graph G is a sequence (T1,...,Tt) of pairwise disjoint non-empty connected subgraphs of G, such that for 1 ≤ i < j ≤ t, every vertex in Tj has a neighbor in Ti. Replacing “every vertex in Tj” by “some vertex in Tj” retrieves the standard definition of a Kt minor. The strengthened notion was introduced in 2024 by Illingworth and Wood, who asked whether every graph with chromatic number t contains a dominating Kt minor. This is a substantial strengthening of the celebrated Hadwiger’s Conjecture, which asserts that every graph with chromatic number t contains a Kt minor. Sergey Norin referred to this question as the “Dominating Hadwiger’s Conjecture” and believes it is likely false. In this talk, we present our recent work on the Dominating Hadwiger’s Conjecture and discuss the key ideas of our results.
Joint work with Michael Scully and Thomas Tibbetts.
Xingxing Yu, Georgia Institute of Technology
Title: Edge coloring multigraphs in polynomial time
Abstract: For a multigraph $G$, let $\chi'(G)$ denote the chromatic index of $G$, let $\Delta(G)$ be the maximum degree of $G$, and let $\Gamma(G) = \max\{\lceil 2|E(H)|/(|V (H)|-1)\rceil: H \subseteq G \mbox{ and } |V(H)| \ge 2\}$. As a generalization of Vizing’s classical coloring result for simple graphs, the Goldberg-Seymour conjecture, posed around 1973, asserts that $\chi'(G)=\max\{\Delta(G), \Gamma(G)\}$ or $\chi'(G)=\max\{\Delta(G) + 1, \Gamma(G)\}$. Hochbaum, Nishizeki, and Shmoys conjectured in 1986 that a $\max\{\Delta(G) + 1, \chi'(G)\}$-edge-coloring of $G$ can be found in polynomial time in the size of $G$. We give a polynomial time algorithm for finding a $\max\{\Delta(G) + 1, \Gamma(G)\}$-edge-coloring of $G$, confirming both conjectures. Joint work with G. Chen, Y. Hao, and W. Zang.