{
  "id": "1602.04316",
  "version": "v1",
  "published": "2016-02-13T11:19:24.000Z",
  "updated": "2016-02-13T11:19:24.000Z",
  "title": "Half-regular factorizations of the complete bipartite graph",
  "authors": [
    "Mark Aksen",
    "Istvan Miklos",
    "Kathleen Zhou"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider a bipartite version of the color degree matrix problem. A bipartite graph $G(U,V,E)$ is half-regular if all vertices in $U$ have the same degree. We give necessary and sufficient conditions for a bipartite degree matrix (also known as demand matrix) to be the color degree matrix of an edge-disjoint union of half-regular graphs. We also give necessary and sufficient perturbations to transform realizations of a half-regular degree matrix into each other. Based on these perturbations, a Markov chain Monte Carlo method is designed in which the inverse of the acceptance ratios are polynomial bounded. Realizations of a half-regular degree matrix are generalizations of Latin squares, and they also appear in applied neuroscience.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-02-13T11:19:24.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C07"
    ],
    "keywords": [
      "complete bipartite graph",
      "half-regular factorizations",
      "half-regular degree matrix",
      "markov chain monte carlo method",
      "color degree matrix problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}