Sesión Matemática Discreta y Teoría de JuegosDominating \(K_t\) models in Kneser graphs
Adrian Pastine
Universidad Nacional de San Luis, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Hadwiger’s conjecture (1943) states that every graph \(G\) has a \(K_{\chi(G)}\) minor, where \(\chi(G)\) denotes the chromatic number of \(G\). This is a generalization of the Four Color Theorem. Over the years, several strengthenings and weakenings of the conjecture have been studied. The problem of dominating \(K_t\) models is one such strengthening.
A dominating \(K_t\) model is a sequence \((T_1,\ldots,T_t)\) such that each \(T_i\) is a connected subgraph and, for every \(1\leq i\leq j\leq t\), every vertex of \(T_j\) has a neighbor in \(T_i\). Dominating \(K_t\) models were introduced in [1] as a stronger version of Hadwiger’s conjecture.
The Kneser graph \(KG(2k+r,k)\) has as its vertices the \(k\)-subsets of a set of size \(2k+r\), with two vertices adjacent if and only if the corresponding subsets are disjoint. Kneser graphs are interesting from a topological point of view and have played an important role in the study of variations of Hadwiger’s conjecture. In particular, they provide a natural setting in which to investigate stronger notions of complete minors. Recall that [ (KG(2k+r,k))=r+2. ] Recent results on odd subdivisions, which provide a stronger structure than a complete minor, also show that Kneser graphs contain large complete structures: for \(k\geq 13\) and \(r\geq 6\), with \(2r\mid(k-1)\), \(KG(2k+r,k)\) contains \(K_{\lceil(k+r)/8\rceil}\) as a totally odd subdivision.
In this talk, we study dominating \(K_t\) models in Kneser graphs. We present two such models. The first has size [ t=(r-2-2), ] for every positive integer \(\ell\) such that \(r-2\ell-3\geq 0\). The second has size [ +1. ] These two constructions are complementary: depending on the relative size of \(r\) and \(k\), one of them can provide a larger dominating model than the other.
Trabajo en conjunto con: Agustina Ledezma (Universidad Nacional de San Luis), Andrea Jiménez (Universidad de Valparaiso), Benjamin Moore (University of Manitoba) y Daniel Quiroz (Universidad de Valparaiso).
Referencias
[1] Illingworth, F. and Wood, D.R. (2025), Dominating $K_t$-Models. Journal of Graph Theory, 110: 448-456. https://doi.org/10.1002/jgt.23272