RECORD
Singular Tur\'an numbers and WORM-colorings
Combinatorics · Submitted 11 Sep 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We determine $T_S(n,K_3)$ for all $n\equiv 0$ (mod 4) and $n\equiv 1$ (mod 4), and also $T_S(n,K_{r+1})$ for large enough $n$ that is divisible by $r$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
A subgraph $H$ of $G$ is \textit{singular} if the vertices of $H$ either have the same degree in $G$ or have pairwise distinct degrees in $G$. The largest number of edges of a graph on $n$ vertices that does not contain a singular copy of $H$ is denoted by $T_S(n,H)$. Caro and Tuza [Theory and Applications of Graphs, 6 (2019), 1--32] obtained the asymptotics of $T_S(n,H)$ for every graph $H$, but determined the exact value of this function only in the case $H=K_3$ and $n\equiv 2$ (mod 4). We determine $T_S(n,K_3)$ for all $n\equiv 0$ (mod 4) and $n\equiv 1$ (mod 4), and also $T_S(n,K_{r+1})$ for large enough $n$ that is divisible by $r$. We also explore the connection to the so-called $H$-WORM colorings (colorings without rainbow or monochromatic copies of $H$) and obtain new results regarding the largest number of edges that a graph with an $H$-WORM coloring can have.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | A subgraph $H$ of $G$ is \textit{singular} if the vertices of $H$ either have the same degree in $G$ or have pairwise distinct degrees in $G$. | background 1.00 | 0.13 | 0.02 | asserted 0.99 |
| s1 | The largest number of edges of a graph on $n$ vertices that does not contain a singular copy of $H$ is denoted by $T_S(n,H)$. | background 1.00 | 0.07 | 0.03 | asserted 0.96 |
| s2 | Caro and Tuza [Theory and Applications of Graphs, 6 (2019), 1--32] obtained the asymptotics of $T_S(n,H)$ for every graph $H$, but determined the exact value of this function only in the case $H=K_3$ and $n\equiv 2$ (mod 4). | gap 0.59 | 0.03 | 0.04 | asserted 1.00 |
| s3 | We determine $T_S(n,K_3)$ for all $n\equiv 0$ (mod 4) and $n\equiv 1$ (mod 4), and also $T_S(n,K_{r+1})$ for large enough $n$ that is divisible by $r$. | result 0.57 | 0.97 | 0.83 | asserted 1.00 |
| s4 | We also explore the connection to the so-called $H$-WORM colorings (colorings without rainbow or monochromatic copies of $H$) and obtain new results regarding the largest number of edges that a graph with an $H$-WORM coloring can have. | contribution 0.93 | 0.95 | 0.11 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
A subgraph $H$ of $G$ is \textit{singular} if the vertices of $H$ either have the same degree in $G$ or have pairwise distinct degrees in $G$. The largest number of edges of a graph on $n$ vertices that does not contain a singular copy of $H$ is denoted by $T_S(n,H)$. Caro and Tuza [Theory and Applications of Graphs, 6 (2019), 1--32] obtained the asymptotics of $T_S(n,H)$ for every graph $H$, but determined the exact value of this function only in the case $H=K_3$ and $n\equiv 2$ (mod 4). We determine $T_S(n,K_3)$ for all $n\equiv 0$ (mod 4) and $n\equiv 1$ (mod 4), and also $T_S(n,K_{r+1})$ for large enough $n$ that is divisible by $r$. We also explore the connection to the so-called $H$-WORM colorings (colorings without rainbow or monochromatic copies of $H$) and obtain new results regarding the largest number of edges that a graph with an $H$-WORM coloring can have.
Human review
How the literature uses it
4 arXiv papers cite this in 11 sentences
Papers citing it · 5 sentences without a confident label
Cites it as background 3 papers
-
The regular Turán number was introduced recently by Gerbner, Patkós, Vizer, and the second author in [ref] , motivated by the study of singular Turán numbers introduced in [ref] .
Regular Tur\'an numbers · Introduction · 0.97
-
For other graphs, regular Turán numbers were introduced and studied systematically in [ref] .
Regular Tur\'an numbers of complete bipartite graphs · Introduction · 0.89
-
With a different application in mind, the regular Turán number was introduced in [ref] in an alternative formulation as the maximum number of edges in a regular $H$-free graph: $(n,H)=2/n _r(n,H)$.
Regular Tur\'an numbers and some Gan-Loh-Sudakov-type problems · Notes added · 0.94
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.