Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2409.11152 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910619069841408 |
|---|---|
| author | Janzer, Oliver Yip, Fredy |
| author_facet | Janzer, Oliver Yip, Fredy |
| contents | A graph $G$ with an even number of edges is called even-decomposable if there is a sequence $V(G)=V_0\supset V_1\supset \dots \supset V_k=\emptyset$ such that for each $i$, $G[V_i]$ has an even number of edges and $V_i\setminus~V_{i+1}$ is an independent set in $G$. The study of this property was initiated recently by Versteegen, motivated by connections to a Ramsey-type problem and questions about graph codes posed by Alon. Resolving a conjecture of Versteegen, we prove that all but an $e^{-Ω(n^2)}$ proportion of the $n$-vertex graphs with an even number of edges are even-decomposable. Moreover, answering one of his questions, we determine the order of magnitude of the smallest $p=p(n)$ for which the probability that the random graph $G(n,1-p)$ is even-decomposable (conditional on it having an even number of edges) is at least $1/2$.
We also study the following closely related property. A graph is called even-degenerate if there is an ordering $v_1,v_2,\dots,v_n$ of its vertices such that each $v_i$ has an even number of neighbours in the set $\{v_{i+1},\dots,v_n\}$. We prove that all but an $e^{-Ω(n)}$ proportion of the $n$-vertex graphs with an even number of edges are even-degenerate, which is tight up to the implied constant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11152 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The probability that a random graph is even-decomposable Janzer, Oliver Yip, Fredy Combinatorics A graph $G$ with an even number of edges is called even-decomposable if there is a sequence $V(G)=V_0\supset V_1\supset \dots \supset V_k=\emptyset$ such that for each $i$, $G[V_i]$ has an even number of edges and $V_i\setminus~V_{i+1}$ is an independent set in $G$. The study of this property was initiated recently by Versteegen, motivated by connections to a Ramsey-type problem and questions about graph codes posed by Alon. Resolving a conjecture of Versteegen, we prove that all but an $e^{-Ω(n^2)}$ proportion of the $n$-vertex graphs with an even number of edges are even-decomposable. Moreover, answering one of his questions, we determine the order of magnitude of the smallest $p=p(n)$ for which the probability that the random graph $G(n,1-p)$ is even-decomposable (conditional on it having an even number of edges) is at least $1/2$. We also study the following closely related property. A graph is called even-degenerate if there is an ordering $v_1,v_2,\dots,v_n$ of its vertices such that each $v_i$ has an even number of neighbours in the set $\{v_{i+1},\dots,v_n\}$. We prove that all but an $e^{-Ω(n)}$ proportion of the $n$-vertex graphs with an even number of edges are even-degenerate, which is tight up to the implied constant. |
| title | The probability that a random graph is even-decomposable |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.11152 |