Leírás
With Yair Caro we study new versions of classical extremal problems, imposing additional constraints on vertex degrees. We say that a set $S$ of vertices in a graph $G$ is singular if either all vertices of $S$ have the same degree in $G$, or all have distinct degrees. A subgraph is singular if its vertex set is singular.
The singular Ramsey number of a graph $F$, denoted by $Rs(F)$, is the smallest n such that for every m at least n, in every 2-coloring of the edges of the complete graph $K_m$ of order $m$ the graph formed by the edges of some color class contains a singular subgraph isomorphic to $F$. A similar approach to Turán problems excludes singular subgraphs isomorphic to $F$ and asks for the maximum number $Ts(n,F)$ of edges.
We prove general estimates, asymptotic bounds, and tight results. For example, $Rs(K_3)=22$.