{
  "id": "1303.5622",
  "version": "v1",
  "published": "2013-03-22T14:17:03.000Z",
  "updated": "2013-03-22T14:17:03.000Z",
  "title": "On the approximate shape of degree sequences that are not potentially $H$-graphic",
  "authors": [
    "Catherine Erbes",
    "Michael Ferrara",
    "Ryan R. Martin",
    "Paul Wenger"
  ],
  "comment": "19 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A sequence of nonnegative integers $\\pi$ is {\\it graphic} if it is the degree sequence of some graph $G$. In this case we say that $G$ is a \\textit{realization} of $\\pi$, and we write $\\pi=\\pi(G)$. A graphic sequence $\\pi$ is {\\it potentially $H$-graphic} if there is a realization of $\\pi$ that contains $H$ as a subgraph. Given nonincreasing graphic sequences $\\pi_1=(d_1,\\ldots,d_n)$ and $\\pi_2 = (s_1,\\ldots,s_n)$, we say that $\\pi_1$ {\\it majorizes} $\\pi_2$ if $d_i \\geq s_i$ for all $i$, $1 \\leq i \\leq n$. In 1970, Erd\\H{o}s showed that for any $K_{r+1}$-free graph $H$, there exists an $r$-partite graph $G$ such that $\\pi(G)$ majorizes $\\pi(H)$. In 2005, Pikhurko and Taraz generalized this notion and showed that for any graph $F$ with chromatic number $r+1$, the degree sequence of an $F$-free graph is, in an appropriate sense, nearly majorized by the degree sequence of an $r$-partite graph. In this paper, we give similar results for degree sequences that are not potentially $H$-graphic. In particular, there is a graphic sequence $\\pi^*(H)$ such that if $\\pi$ is a graphic sequence that is not potentially $H$-graphic, then $\\pi$ is close to being majorized by $\\pi^*(H)$. Similar to the role played by complete multipartite graphs in the traditional extremal setting, the sequence $\\pi^*(H)$ asymptotically gives the maximum possible sum of a graphic sequence $\\pi$ that is not potentially $H$-graphic.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-03-22T14:17:03.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C07",
      "05C35"
    ],
    "keywords": [
      "degree sequence",
      "approximate shape",
      "free graph",
      "complete multipartite graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1303.5622E"
    }
  }
}