Singular Ramsey and Turán numbers

Abstract: We say that a subgraph

F

of a graph

G

is singular if the degrees

d_{G} (v)

are all equal or all distinct for the vertices

v i n V (F)

. The singular Ramsey number Rs

(F)

is the smallest positive integer

n

such that, for every

m g e q n

, in every edge 2-coloring of

K_{m}

, at least one of the color classes contains

F

as a singular subgraph. In a similar flavor, the singular Tur'an number Ts

(n, F)

is defined as the maximum number of edges in a graph of order

n

, which does not contain

F

as a singular subgraph. In this paper we initiate the study of these extremal problems. We develop methods to estimate Rs

(F)

and Ts

(n, F)

, present tight asymptotic bounds and exact results.

Recommendations

Cited in

(6)

This page was built for publication: Singular Ramsey and Turán numbers