In mathematics, crossing numbers arise in two related contexts: in knot theory and in graph theory. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics, knot theory is the area of Topology that studies mathematical knots While inspired by knots which appear in daily life in shoelaces In Mathematics and Computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects

Contents 1 Crossing numbers in knot theory 2 Crossing numbers in graph theory 2.1 History 2.2 Complexity 2.3 Crossing numbers of cubic graphs 2.4 The crossing number inequality 2.4.1 Proof of crossing number inequality 3 References

Crossing numbers in knot theory

In knot theory, the crossing number is an example of a knot invariant. In Mathematics, knot theory is the area of Topology that studies mathematical knots While inspired by knots which appear in daily life in shoelaces In the mathematical field of Knot theory, a knot invariant is a quantity (in a broad sense defined for each knot which is the same for equivalent knots A knot's crossing number is simply the lowest number of crossings of any diagram of the knot. In Mathematics, knot theory is the area of Topology that studies mathematical knots While inspired by knots which appear in daily life in shoelaces

By way of example, the unknot has crossing number zero, the trefoil knot three and the figure-eight knot four. The unknot arises in the mathematical theory of knots. Intuitively the unknot is a closed loop of rope without a Knot in it In Knot theory, the trefoil knot is the simplest nontrivial knot. In Knot theory, a figure-eight knot (also called Listing's knot) is the unique knot with a crossing number of four There are no other knots with a crossing number this low and just two knots have crossing number 5, but the number of knots with a particular crossing number increases rapidly as we go higher.

Tables of prime knots are traditionally indexed by crossing number, with a subscript to indicate which particular knot out of those with this many crossings is meant (this sub-ordering is not based on anything in particular, except that torus knots are listed first). In Knot theory, a prime knot is a knot which is in a certain sense indecomposable In Knot theory, a torus knot is a special kind of knot which lies on the surface of an unknotted Torus in R 3 The listing goes 3₁ (the trefoil knot), 4₁ (the figure-eight knot), 5₁, 5₂, 6₁, etc. This order has not changed significantly since P. G. Tait published a tabulation of knots in 1877. Peter Guthrie Tait ( April 28, 1831 - July 4, 1901) was a Scottish mathematical physicist, best known for the seminal energy Year 1877 ( MDCCCLXXVII) was a Common year starting on Monday (link will display the full calendar of the Gregorian calendar (or a Common

There has been very little progress on understanding the behavior of crossing number under rudimentary operations on knots. A big open question asks if the crossing number is additive under the knot sum. In Mathematics, specifically in Topology, the operation of connected sum is a geometric modification on Manifolds Its effect is to join two given manifolds It is also expected that a satellite of a knot K should have larger crossing number than K, but this has not been proven. In the mathematical theory of knots, a satellite knot is a knot which contains an incompressible, non- Boundary parallel Torus in its

Crossing numbers in graph theory

The crossing number cr(G) of a graph G is the lowest number of crossings of a planar drawing of the graph G. Graph drawing, as a branch of Graph theory, applies Topology and Geometry to derive two-dimensional representations of graphs Graph drawing is For instance, a graph is planar if and only if its crossing number is zero. Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden ↔ Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves; the rectilinear crossing number requires all edges to be straight line segments, and may differ from the crossing number. In particular, the rectilinear crossing number of a complete graph is essentially the same as the minimum number of convex quadrilaterals determined by a set of n points in general position, closely related to the Happy Ending problem. In the mathematical field of Graph theory, a complete graph is a Simple graph in which every pair of distinct vertices is connected by an ^[1]

History

The problem of the crossing number of the complete bipartite graph, known as Turan’s brick factory problem, was first posed by Pál Turán, and appears in print in 1954. Paul (Pál Turán ( ( August 18 1910 &ndash September 26 1976)was a Hungarian Mathematician who worked primarily in ^[2] The problem of the crossing number of the complete graph was first posed by Anthony Hill, and appears in print in 1960. ^[3] Interestingly, Anthony Hill and John Ernest were two collaborating constructivist artists fascinated by mathematics who not only formulated this problem but also originated a conjectural upper bound for this crossing number co-published with Richard Guy in 1960. Anthony Hill is an English Artist, painter and Relief-maker, originally a member of the post- World War II British art movement termed John Ernest (1922-1994 was an American born artist working in England from 1951 Richard Kenneth Guy (born 1916 Nuneaton, Warwickshire) is a British mathematician Professor Emeritus in the Department of Mathematics ^[4]

Complexity

In general, determining the crossing number of a graph is hard; Garey and Johnson showed in 1983 that it is an NP-hard problem. Michael R Garey is a Computer science researcher and co-author (with David S David Stifler Johnson (born December 9, 1945) is a Computer scientist specializing in Algorithms and optimization NP-hard (nondeterministic Polynomial-time hard in Computational complexity theory, is a class of problems informally "at least as hard as the hardest problems ^[5] In fact the problem remains NP-hard even when restricted to cubic graphs. In the mathematical field of Graph theory, a cubic graph is a graph where all vertices are incident to exactly three edges ^[6]

On the positive side, there are efficient algorithms for determining if the crossing number is less than a fixed constant k — in other words, the problem is fixed-parameter tractable. In Computer science, parameterized complexity is a measure of complexity of problems with multiple input parameters ^[7] It remains difficult for larger k, such as |V|/2. There are also efficient approximation algorithms for computing the crossing number of graphs of bounded degree. In Computer science and Operations research, approximation algorithms are Algorithms used to find approximate solutions to Optimization problems In practice heuristic algorithms are used, such as the simple algorithm which starts with no edges and continually adds each new edge in a way that produces the fewest additional crossings possible. heuristic (hyu̇-ˈris-tik is a method to help solve a problem commonly an informal method

Crossing numbers of cubic graphs

The smallest cubic graphs with crossing numbers 1–6 are known (sequence A110507 in OEIS). In the mathematical field of Graph theory, a cubic graph is a graph where all vertices are incident to exactly three edges The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences The smallest 1-crossing graph is the complete bipartite graph K_3,3, with 6 vertices. In the Mathematical field of Graph theory, a complete bipartite graph or biclique is a special kind of Bipartite graph where every The smallest 2-crossing graph is the Petersen graph, with 10 vertices. In Graph theory, the Petersen graph is an Undirected graph with 10 vertices and 15 edges The smallest 3-crossing graph is the Heawood graph, with 14 vertices. In the mathematical field of Graph theory, the Heawood graph is an Undirected graph with 14 vertices and 21 edges The smallest 4-crossing graph is the Möbius-Kantor graph, with 16 vertices. In Graph theory, the Möbius–Kantor graph is a symmetric bipartite Cubic graph with 16 vertices and 24 edges The smallest 5-crossing graph is the Pappus graph, with 18 vertices. In the mathematical field of Graph theory, the Pappus graph is a 3- Regular graph with 18 vertices and 27 edges formed as the Levi graph And the smallest 6-crossing graph is the Desargues graph, with 20 vertices. In the mathematical field of Graph theory, the Desargues graph is a 3- Regular graph with 20 vertices and 30 edges formed as the Levi graph of

The crossing number inequality

The very useful crossing number inequality, discovered independently by Ajtai, Chvátal, Newborn, and Szemerédi^[8] and by Leighton^[9], asserts that if a graph G (undirected, with no loops or multiple edges) with n vertices and e edges has many edges, in the sense that if

then we have

The constant 33. Václav (Vašek Chvátal (born 1946 (ˈvaːt͡slaf ˈxvaːtal is a professor in the Department of Computer Science and Software Engineering at Concordia University in 75 is the best known to date, and is due to Pach and Tóth;^[10] the constant 7. 5 can be lowered to 4, but at the expense of replacing 33. 75 with the worse constant of 64.

The motivation of Leighton in studying crossing numbers was for applications to VLSI design in theoretical computer science. Later, Székely^[11] also realized that this inequality yielded very simple proofs of some important theorems in incidence geometry, such as Beck's theorem and the Szemerédi-Trotter theorem, and Tamal Dey used it to prove upper bounds on geometric k-sets. In Geometry, the Relations of incidence are those such as 'lies on' between points and lines (as in 'point P lies on line L' and 'intersects' (as in 'line L1 In Incidence geometry, Beck's theorem is a more quantitative form of the more classical Sylvester–Gallai theorem. In Mathematics, the Szemerédi–Trotter theorem is a result in the field of Combinatorial geometry. In Discrete geometry, a k -set of a finite point set S in the Euclidean plane is a Subset of k elements of S that can be ^[12]

Proof of crossing number inequality

We first give a preliminary estimate: for any graph G with n vertices and e edges, we have

To prove this, consider a diagram of G which has exactly cr(G) crossings. Each of these crossings can be removed by removing an edge from G. Thus we can find a graph with at least edges and n vertices with no crossings, and is thus a planar graph. Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden But from Euler's formula we must then have , and the claim follows. Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden (In fact we have for n ≥ 3).

To obtain the actual crossing number inequality, we now use a probabilistic argument. This article is not about Probabilistic algorithms which give the right answer with high probability but not with certainty nor about Monte We let 0 < p < 1 be a probability parameter to be chosen later, and construct a random subgraph H of G by allowing each vertex of G to lie in H independently with probability p, and allowing an edge of G to lie in H if and only if its two vertices were chosen to lie in H. Probability is the likelihood or chance that something is the case or will happen In Mathematics, a random graph is a graph that is generated by some Random process. Let e_H denote the number of edges of H, and let n_H denote the number of vertices.

Now consider a diagram of G with cr(G) crossings. We may assume that any two edges in this diagram with a common vertex are disjoint, otherwise we could interchange the intersecting parts of the two edges and reduce the crossing number by one. Thus every crossing in this diagram involves four distinct vertices of G.

Since H is a subgraph of G, this diagram contains a diagram of H; let denote the number of crossings of this random graph. By the preliminary crossing number inequality, we have

Taking expectations we obtain

Since each of the n vertices in G had a probability p of being in H, we have . Similarly, since each of the edges in G has a probability p² of remaining in H (since both endpoints need to stay in H), then . Finally, every crossing in the diagram of G has a probability p⁴ of remaining in H, since every crossing involves four vertices, and so . Thus we have

If we now set p to equal 4n/e (which is less than one, since we assume that e is greater than 4n), we obtain after some algebra

A slight refinement of this argument allows one to replace 64 by 33. 75 when e is greater than 7. 5 n. ^[10]

References

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic