Minimum clique number, chromatic number, and Ramsey numbers (Q426827): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:14, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimum clique number, chromatic number, and Ramsey numbers |
scientific article |
Statements
Minimum clique number, chromatic number, and Ramsey numbers (English)
0 references
12 June 2012
0 references
Summary: Let \(Q(n,c)\) denote the minimum clique number over graphs with \(n\) vertices and chromatic number \(c\). We investigate the asymptotics of \(Q(n,c)\) when \(n/c\) is held constant. We show that when \(n/c\) is an integer \(\alpha, Q(n,c)\) has the same growth order as the inverse function of the Ramsey number \(R(\alpha+1,t)\) (as a function of \(t\)). Furthermore, we show that if certain asymptotic properties of the Ramsey numbers hold, then \(Q(n,c)\) is in fact asymptotically equivalent to the aforementioned inverse function. We use this fact to deduce that \(Q(n,\lceil n/3 \rceil)\) is asymptotically equivalent to the inverse function of \(R(4,t)\).
0 references
asymptotic properties of the Ramsey numbers
0 references