Degree criteria and stability for independent transversals
An \emph{independent transversal} (IT) in a graph $G$ with a given vertex partition $P$ is an independent set of vertices of $G$ (i.e. it induces no edges), that consists of one vertex from each part (\emph{block}) of $P$. Over the years, various criteria have been established that guarantee the exi...
Main Authors: | , |
---|---|
Format: | Text |
Language: | unknown |
Published: |
2023
|
Subjects: | |
Online Access: | http://arxiv.org/abs/2305.10595 |
id |
ftarxivpreprints:oai:arXiv.org:2305.10595 |
---|---|
record_format |
openpolar |
spelling |
ftarxivpreprints:oai:arXiv.org:2305.10595 2023-09-05T13:19:58+02:00 Degree criteria and stability for independent transversals Haxell, Penny Wdowinski, Ronen 2023-05-17 http://arxiv.org/abs/2305.10595 unknown http://arxiv.org/abs/2305.10595 Mathematics - Combinatorics text 2023 ftarxivpreprints 2023-08-16T17:42:31Z An \emph{independent transversal} (IT) in a graph $G$ with a given vertex partition $P$ is an independent set of vertices of $G$ (i.e. it induces no edges), that consists of one vertex from each part (\emph{block}) of $P$. Over the years, various criteria have been established that guarantee the existence of an IT, often given in terms of $P$ being $t$-\emph{thick}, meaning all blocks have size at least $t$. One such result, obtained recently by Wanless and Wood, is based on the \emph{maximum average block degree} $b(G,P)=\max\{\sum_{u\in U} d(u)/|U| : U \in P\}$. They proved that if $b(G,P)\leq t/4$ then an IT exists. Resolving a problem posed by Groenland, Kaiser, Treffers and Wales (who showed that the ratio $1/4$ is best possible), here we give a full characterization of pairs $(\alpha,\beta)$ such that the following holds for every $t>0$: whenever $G$ is a graph with maximum degree $\Delta(G)\leq\alpha t$, and $P$ is a $t$-thick vertex partition of $G$ such that $b(G,P)\leq \beta t$, there exists an IT of $G$ with respect to $P$. Our proof makes use of another previously known criterion for the existence of IT's that involves the topological connectedness of the independence complex of graphs, and establishes a general technical theorem on the structure of graphs for which this parameter is bounded above by a known quantity. Our result interpolates between the criterion $b(G,P)\leq t/4$ and the old and frequently applied theorem that if $\Delta(G)\leq t/2$ then an IT exists. Using the same approach, we also extend a theorem of Aharoni, Holzman, Howard and Spr\"ussel, by giving a stability version of the latter result. Text Groenland ArXiv.org (Cornell University Library) |
institution |
Open Polar |
collection |
ArXiv.org (Cornell University Library) |
op_collection_id |
ftarxivpreprints |
language |
unknown |
topic |
Mathematics - Combinatorics |
spellingShingle |
Mathematics - Combinatorics Haxell, Penny Wdowinski, Ronen Degree criteria and stability for independent transversals |
topic_facet |
Mathematics - Combinatorics |
description |
An \emph{independent transversal} (IT) in a graph $G$ with a given vertex partition $P$ is an independent set of vertices of $G$ (i.e. it induces no edges), that consists of one vertex from each part (\emph{block}) of $P$. Over the years, various criteria have been established that guarantee the existence of an IT, often given in terms of $P$ being $t$-\emph{thick}, meaning all blocks have size at least $t$. One such result, obtained recently by Wanless and Wood, is based on the \emph{maximum average block degree} $b(G,P)=\max\{\sum_{u\in U} d(u)/|U| : U \in P\}$. They proved that if $b(G,P)\leq t/4$ then an IT exists. Resolving a problem posed by Groenland, Kaiser, Treffers and Wales (who showed that the ratio $1/4$ is best possible), here we give a full characterization of pairs $(\alpha,\beta)$ such that the following holds for every $t>0$: whenever $G$ is a graph with maximum degree $\Delta(G)\leq\alpha t$, and $P$ is a $t$-thick vertex partition of $G$ such that $b(G,P)\leq \beta t$, there exists an IT of $G$ with respect to $P$. Our proof makes use of another previously known criterion for the existence of IT's that involves the topological connectedness of the independence complex of graphs, and establishes a general technical theorem on the structure of graphs for which this parameter is bounded above by a known quantity. Our result interpolates between the criterion $b(G,P)\leq t/4$ and the old and frequently applied theorem that if $\Delta(G)\leq t/2$ then an IT exists. Using the same approach, we also extend a theorem of Aharoni, Holzman, Howard and Spr\"ussel, by giving a stability version of the latter result. |
format |
Text |
author |
Haxell, Penny Wdowinski, Ronen |
author_facet |
Haxell, Penny Wdowinski, Ronen |
author_sort |
Haxell, Penny |
title |
Degree criteria and stability for independent transversals |
title_short |
Degree criteria and stability for independent transversals |
title_full |
Degree criteria and stability for independent transversals |
title_fullStr |
Degree criteria and stability for independent transversals |
title_full_unstemmed |
Degree criteria and stability for independent transversals |
title_sort |
degree criteria and stability for independent transversals |
publishDate |
2023 |
url |
http://arxiv.org/abs/2305.10595 |
genre |
Groenland |
genre_facet |
Groenland |
op_relation |
http://arxiv.org/abs/2305.10595 |
_version_ |
1776200732282716160 |