Critical subgraphs of Schrijver graphs and projective quadrangulations
报告学者:Tomas Kaiser 教授
报告者单位:University of West Bohemia
报告时间:2024年10月25日(周五)下午14:30--15:30
报告地点: Zoom number 7226806999
报告摘要:In this talk, we will review the definitions and main results related to the notion of quadrangulation of a projective space, introduced in the paper of Matej Stehl?k and the speaker. Our starting point is the result of Youngs that every nonbipartite quadrangulation of the projective plane is 4-chromatic. We will show how the generalised notion of projective quadrangulation allows for a natural extension of this result to higher dimensions. We will then show that the Mycielski graphs can be realised as projective quadrangulations in the appropriate dimension, obtaining as a corollary the result of Lovasz which determined the chromatic number of Kneser graphs in 1978. Soon after Lovasz’ breakthrough, Schrijver described a related family of graphs now called Schrijver graphs. For each Kneser graph G, the corresponding Schrijver graph is a vertex-critical subgraph of G with the same chromatic number. Focusing on Schrijver graphs, we will outline a construction showing that SG(n, k) contains a spanning subgraph XG(n, k) that is a quadrangulation of the projective space of dimension n 2k. It turns out that these graphs have a natural combinatorial description, which we will review in the case k =2. Moreover, all the graphs XG(n, k) are edge-critical, a property that chrijver graphs lack except for the trivial cases. Thus, the construction can be viewed as the next step in the direction set by Schrijver’s result.
The talk is based on joint work with Matej Stehl?k.
报告者简介:Tomas Kaiser, Professor in Applied Mathematics, Department of Mathematics of University of West Bohemia. His research interests: chromatic graph theory, structure of cycles in graphs, discrete geometry, topological methods in combinatorics 60 talks at international conferences and workshops. He have many Grants such as Ministry of Education of the Czech Republic. He is managing Editor of the Journal of Graph Theory since 2022; Section Editor of Discrete Mathematics and Theoretical Computer Science. He is a member of the European Mathematical Society.