{
  "id": "2305.10595",
  "version": "v1",
  "published": "2023-05-17T22:06:50.000Z",
  "updated": "2023-05-17T22:06:50.000Z",
  "title": "Degree criteria and stability for independent transversals",
  "authors": [
    "Penny Haxell",
    "Ronen Wdowinski"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-05-17T22:06:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "independent transversals",
      "degree criteria",
      "thick vertex partition",
      "average block degree",
      "full characterization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}