Minimum clique number, chromatic number, and Ramsey numbers (Q426827): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
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)\). | |||
Property / review text: 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)\). / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C69 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C55 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05D10 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6045679 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
asymptotic properties of the Ramsey numbers | |||
Property / zbMATH Keywords: asymptotic properties of the Ramsey numbers / rank | |||
Normal rank |
Revision as of 22:58, 29 June 2023
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