New bounds on crossing numbers (Q1591053): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: János Pach / rank | |||
Property / author | |||
Property / author: Q1164070 / rank | |||
Property / author | |||
Property / author: Géza Tóth / rank | |||
Property / reviewed by | |||
Property / reviewed by: Arthur T. White / rank | |||
Property / author | |||
Property / author: János Pach / rank | |||
Normal rank | |||
Property / author | |||
Property / author: J. H. Spencer / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Géza Tóth / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Arthur T. White / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s004540010011 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W4249905773 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 22:08, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New bounds on crossing numbers |
scientific article |
Statements
New bounds on crossing numbers (English)
0 references
28 June 2001
0 references
The notation \(f(n)\ll g(n)\) means that, as \(n\) goes to infinity, \(g(n)/f(n)\) goes to infinity also. For \(g\geq 0\), let \(S_g\) denote the closed orientable 2-manifold of genus \(g\), with \(\text{cr}_g(G)\) the minimum number of crossing points among all drawings of the graph \(G\) on \(S_g\). Finally, let \(\kappa_g(n,e)\) be the minimum \(\text{cr}_g(G)\), over all graphs \(G\) of order \(n\) and size at least \(e\). The authors show that, if \(n\ll e\ll n^2\), then the limit, as \(n\) goes to infinity, of \(\kappa_g(n, e)n^2/e^3\) is a positive constant \(C\) (independent of \(g\)). The case \(g= 0\) affirms a conjecture of \textit{P. Erdős} and \textit{R. K. Guy} [Am. Math. Mon. 80, 52-68 (1973; Zbl 0264.05109)]. The present authors also show that if \(G\) has order \(n\) and size \(e\geq 4n\), but no 4-cycle (respectively no 6-cycle), then \(\text{cr}_0(G)\geq ce^4/n^3\) (respectively \(ce^5/n^4\)), for a suitable constant \(c> 0\).
0 references
2-manifold of genus
0 references
crossing points
0 references
drawings
0 references