Improved bounds for the crossing numbers of K_m,n and K_n
| Autor: | John Maharry, Dmitrii V. Pasechnik, R. B. Richter, E. de Klerk, Gelasio Salazar |
|---|---|
| Přispěvatelé: | School of Physical and Mathematical Sciences, Research Group: Operations Research, Econometrics and Operations Research |
| Jazyk: | angličtina |
| Rok vydání: | 2004 |
| Předmět: |
05C10
05C62 90C22 90C25 57M15 68R10 General Mathematics Complete graph ComputingMilieux_LEGALASPECTSOFCOMPUTING Permutation group Complete bipartite graph Upper and lower bounds Invariant theory Combinatorics Optimization and Control (math.OC) FOS: Mathematics Mathematics - Combinatorics Combinatorics (math.CO) Crossing number (graph theory) Science::Mathematics::Applied mathematics [DRNTU] Mathematics - Optimization and Control Mathematics |
| Zdroj: | SIAM Journal on Discrete Mathematics, 20(1), 189-202. Society for Industrial and Applied Mathematics Publications Tilburg University-PURE |
| ISSN: | 0895-4801 |
| Popis: | It has been long--conjectured that the crossing number cr(K_m,n) of the complete bipartite graph K_m,n equals the Zarankiewicz Number Z(m,n):= floor((m-1)/2) floor(m/2) floor((n-1)/2) floor(n/2). Another long--standing conjecture states that the crossing number cr(K_n) of the complete graph K_n equals Z(n):= floor(n/2) floor((n-1)/2) floor((n-2)/2) floor((n-3)/2)/4. In this paper we show the following improved bounds on the asymptotic ratios of these crossing numbers and their conjectured values: (i) for each fixed m >= 9, lim_{n->infty} cr(K_m,n)/Z(m,n) >= 0.83m/(m-1); (ii) lim_{n->infty} cr(K_n,n)/Z(n,n) >= 0.83; and (iii) lim_{n->infty} cr(K_n)/Z(n) >= 0.83. The previous best known lower bounds were 0.8m/(m-1), 0.8, and 0.8, respectively. These improved bounds are obtained as a consequence of the new bound cr(K_{7,n}) >= 2.1796n^2 - 4.5n. To obtain this improved lower bound for cr(K_{7,n}), we use some elementary topological facts on drawings of K_{2,7} to set up a quadratic program on 6! variables whose minimum p satisfies cr(K_{7,n}) >= (p/2)n^2 - 4.5n, and then use state--of--the--art quadratic optimization techniques combined with a bit of invariant theory of permutation groups to show that p >= 4.3593. LaTeX, 18 pages, 2 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|