Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



Re: A topological problem
Posted:
Feb 28, 2013 1:03 AM


On Feb 26, 7:17 pm, <fc3a...@unihamburg.de> wrote: > Warning, incoming lousy ASCII, change to fixed font :) > > o o o >    >  O  > \ /\ / > X  X > / \/ \ >  O  >    > o o o > > The lines /\ are tied to the unmovable nodes Oo. > (As you see, four lines come out of O and one out of o.) > X denotes a crossing, which is like a virtual crossing > from knot theory, i.e. you can move it ad lib and any > line over any other. Should they cross in the process, > well duh, then you have more crossings.) > > Can you move the lines around such that no horizontal > line going through this graph cuts more than three > of these lines? I think no, but can you lend me a > formal proof? >  > Hauke Reddmann <:EX8 fc3a...@unihamburg.de > Die Weltformel: IQ+dB=const.
Proofs in knot theory aren't my thing , but here's a shot : Label the knots with numbers :
1 1 1     2  \ /\ / X  X / \/ \  3     4 4 4
denoting four 'levels of height' . 1 path directly connects 4 to 3 2 paths directly connect 4 to 2
If you choose a horizontal coordinate for your line situated between k and (k+1) levels of height, your line will cross at least all the paths taken from m to n , for all m <= k and all n>=(k+1) .
So the minimum number of paths cut between 4 and 3 is 2+1 = 3 Analogous reasoning shows the minimum number of paths between 2 and 3 is : 2 paths from 4  2 + 2 paths from 1  3 + 1 path from 2 3 = five paths .
As shown in a previous post , it is indeed possible to rearrange the lines so that paths 'appear to coincide' , o o o \/ O  O /\ o o o
but whether this is considered 'cheating' or not is another manner .



