{
  "id": "1411.1749",
  "version": "v1",
  "published": "2014-11-06T20:58:35.000Z",
  "updated": "2014-11-06T20:58:35.000Z",
  "title": "Frustrated Triangles",
  "authors": [
    "Teeradej Kittipassorn",
    "Gabor Meszaros"
  ],
  "comment": "18 pages, 4 figures, submitted",
  "categories": [
    "math.CO"
  ],
  "abstract": "A triple of vertices in a graph is a frustrated triangle if it induces an odd number of edges. We study the set $F_n\\subset[0,\\binom{n}{3}]$ of possible number of frustrated triangles $f(G)$ in a graph $G$ on $n$ vertices. We prove that about two thirds of the numbers in $[0,n^{3/2}]$ cannot appear in $F_n$, and we characterise the graphs $G$ with $f(G)\\in[0,n^{3/2}]$. More precisely, our main result is that, for each $n\\geq 3$, $F_n$ contains two interlacing sequences $0=a_0\\leq b_0\\leq a_1\\leq b_1\\leq \\dots \\leq a_m\\leq b_m\\sim n^{3/2}$ such that $F_n\\cap(b_t,a_{t+1})=\\emptyset$ for all $t$, where the gaps are $|b_t-a_{t+1}|=(n-2)-t(t+1)$ and $|a_t-b_t|=t(t-1)$. Moreover, $f(G)\\in[a_t,b_t]$ if and only if $G$ can be obtained from a complete bipartite graph by flipping exactly $t$ edges/nonedges. On the other hand, we show, for all $n$ sufficiently large, that if $m\\in[2\\sqrt{2}n^{3/2},\\binom{n}{3}-2\\sqrt{2}n^{3/2}]$ and $(n+1)m$ is even, then $m\\in F_n$. Furthermore, we determine the graphs with the minimum number of frustrated triangles amongst those with $n$ vertices and $e\\leq n^2/4$ edges.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-11-06T20:58:35.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C15"
    ],
    "keywords": [
      "frustrated triangle",
      "complete bipartite graph",
      "minimum number",
      "odd number",
      "main result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1411.1749K"
    }
  }
}