{
  "id": "2501.00157",
  "version": "v1",
  "published": "2024-12-30T22:02:05.000Z",
  "updated": "2024-12-30T22:02:05.000Z",
  "title": "Alon-Tarsi for hypergraphs",
  "authors": [
    "Marcin Anholcer",
    "Bartłomiej Bosek",
    "Grzegorz Gutowski",
    "Michał Lasoń",
    "Jakub Przybyło",
    "Oriol Serra",
    "Michał Tuczyński",
    "Lluís Vena",
    "Mariusz Zając"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Given a hypergraph $H=(V,E)$, define for every edge $e\\in E$ a linear expression with arguments corresponding with the vertices. Next, let the polynomial $p_H$ be the product of such linear expressions for all edges. Our main goal was to find a relationship between the Alon-Tarsi number of $p_H$ and the edge density of $H$. We prove that $AT(p_H)=\\lceil ed(H)\\rceil+1$ if all the coefficients in $p_H$ are equal to $1$. Our main result is that, no matter what those coefficients are, they can be permuted within the edges so that for the resulting polynomial $p_H^\\prime$, $AT(p_H^\\prime)\\leq 2\\lceil ed(H)\\rceil+1$ holds. We conjecture that, in fact, permuting the coefficients is not necessary. If this were true, then in particular a significant generalization of the famous 1-2-3 Conjecture would follow.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-12-30T22:02:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C65",
      "05C31",
      "05D40",
      "05C15"
    ],
    "keywords": [
      "hypergraph",
      "linear expression",
      "coefficients",
      "main goal",
      "significant generalization"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}