{
  "id": "2406.03290",
  "version": "v1",
  "published": "2024-06-05T14:00:11.000Z",
  "updated": "2024-06-05T14:00:11.000Z",
  "title": "Sparse Sets in Triangle-free Graphs",
  "authors": [
    "Tınaz Ekim",
    "Burak Nur Erdem",
    "John Gimbel"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "A set of vertices is $k$-sparse if it induces a graph with a maximum degree of at most $k$. In this missive, we consider the order of the largest $k$-sparse set in a triangle-free graph of fixed order. We show, for example, that every triangle-free graph of order 11 contains a 1-sparse 5-set; every triangle-free graph of order 13 contains a 2-sparse 7-set; and every triangle-free graph of order 8 contains a 3-sparse 6-set. Further, these are all best possible. For fixed $k$, we consider the growth rate of the largest $k$-sparse set of a triangle-free graph of order $n$. Also, we consider Ramsey numbers of the following type. Given $i$, what is the smallest $n$ having the property that all triangle-free graphs of order $n$ contain a 4-cycle or a $k$-sparse set of order $i$. We use both direct proof techniques and an efficient graph enumeration algorithm to obtain several values for defective Ramsey numbers and a parameter related to largest sparse sets in triangle-free graphs, along with their extremal graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-06-05T14:00:11.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "triangle-free graph",
      "efficient graph enumeration algorithm",
      "direct proof techniques",
      "largest sparse sets",
      "extremal graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}