Independent transversals in multipartite graphs

Document Type

Lecture

Publication Date

4-16-2025

Abstract

An independent transversal in a multipartite graph is an independent set that intersects each part in exactly one vertex. We show that for any even integer r > 0, there exist c > 0 and n0 such that every r-partite graph with parts of size n > n0 and maximum degree less than rn/(2r − 2) contains at least cnr−1 independent transversals. This is best possible up to the value of c and confirmed a conjecture of Haxell and Szabo from 2006 and partially answered a question raised by Erdős from 1972. We also show that for integer s > 1, even integer r > 0 there exist c/ > 0 and n0 such that every r-partite graph with parts of size n > n0 and maximum degree less than rn/(2r − 2) − cn1−1/s contains an independent set with exactly s vertices in each part. This is best possible up to the value of c for s = 2, 3 due to known constructions for the Zarankiewicz problem. This is a joint work with Yantao Tang.

Relational Format

presentation

This document is currently not available for download.

Share

COinS