Archive

Archive for the ‘Math’ Category

Legendrian Knot Theory: Lecture 1

May 15, 2012 Leave a comment

-Joan Licata. IAS

Knot theory is an elegant union of topology and geometry. We all know what a knot is.  Let’s look at the mathematical definition.

Defn. A knot is a smooth embedding K: S^1 \rightarrow \mathbb{R}^3

We are only interested in classes of equivalent knots. By equivalent I mean that knots obtained on translating or stretching each other should all be equivalent. This naturally leads to defining an isotopy.

Defn.  K_0, K_1 are isotopic if there is a homotopy  K: S^1X [0,1] \rightarrow \mathbb{R}^3 such that

  • \forall t, H(S^1Xt) is an embedding
  • H(S^1X0)=K_0
  • H(S^1X1)=K_1

This simply means that you can go from one knot to the other by a smooth transformation. Think of ‘t’ as some sort of a parametrisation for the ‘path’ between the two knots.

Projections

On paper, knots are represented by 2-D diagrams called knot diagrams. Of course, we need to show the over and undercrossings to completely describe a knot. This is called a knot diagram. A projection is a diagram without this information. It is the ‘shadow’ of a knot.

Here is a common knot called ‘trefoil’ and its realisation as a physical model.

Fig 1: Isotopic knots: From Left to Right: a, b, c.

Fig 2: Models of the trefoil corresponding to a and b in Fig 1

In Fig 1, a and b are isotopic. One could deform a to get b without cutting the string. c is the Knot projection of b.

So far we have spoken of general knots. Now we come to a very important additional structure that makes Legendrian knots so special.

The standard contact structure

Defn. The standard contact structure \xi_{std} on \mathbb{R}^3 is the 2 plane field such that at (x,y,z),

  • the normal vector is \left[ \begin{array}{c} -y \\ 0\\1\end{array} \right]
  • (equivalent defn) The plane is spanned by \left[ \begin{array}{c} 0 \\1\\ 0\end{array} \right] and \left[ \begin{array}{c} 1\\ 0\\y\end{array} \right]

By a ‘plane field’ we mean that there is a plane associated with each point is space, just like an electric field associates a vector with each point in space. Try sketching these planes in \mathbb{R}^3 .  The planes don’t change along X! It will always be convenient to be an observer on the -Y axis, very far away from the origin, such that we are facing the X-Z plane. This is how the plane field looks.

Fig 3: Standard contact structure

Now we come to the definition on a Legendrian knot.

Defn. K is Legendrian (wrt \xi_{std} if at every point on K, the tangent vector to K lies in \xi_{std}.

Note that this will qualify only certain special knots as Legendrian, of the infinite possibilities. Two Legendrian knots are isotopic if one can be deformed into another while always preserving the Legendrian condition.

See figure 4 for an  example of a Legendrian knot showing the contact structure.

Fig 4: Example of a Legendrian knot showing the contact structure

Defn The projection of a Legendrian knot on the XZ plane is called the front projection.

It would seem that projection would lose out a lot of information (in the Y direction) and make it impossible to reconstruct the knot simply by looking at its shadow. But Legendrian knots are special.  It  turns out that a projection  is enough to reconstruct a Legendrian knot. Let us see why.

Consider a point P on a the front projection of Legendrian knot K. This corresponds to the point P on the actual knot K. Consider the line L tangent to K at P. This line, by definition, must belong to the XZ plane. Moreover, the slope of the line, dz/dx, is nothing but the y-coordinate of P! Therefore the information lost by projecting is retrieved from the slope.

Observe the way the panes twist as one moves along the Y axis in Fig 3. A line on the +Y side of space will be seen having a positive slope in the front projection, a line on the -Y side will be seen to have a negative slope. Hence, just looking at the tangent lines of our front projection, we can tell which how the strands are oriented, which strands are in front and which go behind. You must have noticed that there seems to be a problem when the slope goes to infinity, i.e. for vertical tangents. It’s not really a problems since these appear as cusps in our projection.

Fig 5: Reconstructing a Legendrian knot. From left to right: a, b, c.

Observe figure 5. Let’s start with c. How do we know which of the strands goes behind and which is in the front? Use the thumb rule that the more negative slope is in the front (remember that our observer is at -\infty on the Y axis, facing the XZ plane. Now you can easily see how a and b follow.

In the next lecture I will write about knot invariants.

Advertisements
Categories: Math Tags: ,

Sudoku as a coloured graph

February 28, 2012 6 comments

Prereqs: Just the definition of a graph – vertices, edges and adjacent vertices.

2 years back I gave an exposition on counting the number of unique sudokus, which are not related to each other by the usual symmetry transformations like permuting cells, rows, etc. No more on that. You can read everything you want to know about this on http://www.afjarvis.staff.shef.ac.uk/sudoku/.  By the way, the number is 6670903752021072936960. Yes, it’s large enough to be comforted that you have enough unique sudokus to solve all your life. Unless you’re a computer.

Today I was thinking about how people can build a “well formed” sudoku (that is, one with a unique solution). People, mind you, not a sudoku-builder program that uses incremental or decremental generation to come up with a valid sudoku.

What is the minimum number of elements one needs to specify for the sudoku to have a unique solution?

This is not at all an easy question to answer. You may answer it with some work for a 4*4 sudoku perhaps, but as you increase the size the question becomes way harder.  After thinking and searching for whatever literature I could find about this, I stumbled upon the most elegant solution I’ve seen in a while (Alright, I haven’t seen much. Granted. But this got me intrigued.) I shall discuss below the solution as proposed by Herzberg and Ram Murty in their paper.

Trivia: The minimum number is atmost 17. Nobody knows if a sudoku with 16 entries to start with can have a unique solution.

Basic graph theory in a nutshellI will not be writing about this but you can go to the hyperlink if you need a refresher.

_________________________________________

A sudoku as a coloured graph:

 A coloured graph is a set of vertices and edges, with an addition variable called “colour” which each vertex is assigned. How do we view a sudoku as a coloured graph?

Consider the usual 9*9 sudoku. Number all the cells from 1 through 81. These are your vertices. Now connect them as follows: each vertex is connected to all vertices in the same row, column and square ( by square I mean the 3*3 squares that the sudoku is made up of.) Introduce 9 colours (Girls have the added advantage for visualization here as there are more complex colours on their palette – fuschia, turquoise and what not). Now assign each cell a colour out of these 9. To solve a sudoku, you need to assign these colours such that no two connected vertices have the same colour!

Let’s state this formally.

Proper colouring of a graph

A \lambda- colouring of a graph G is a map f from the vertex set of G to {1,2, \ldots, \lambda} . This is called a proper colouring if f(x) \neq  f(y) whenever x and y are adjacent in G (Adjacent means that the two vertices of the graph are connected by an edge). So a sudoku puzzle is basically an incomplete colouring( called a partial colouring) which the solver needs to complete.

To quote the experts,

“A Sudoku puzzle corresponds to a partial coloring and the question is whether this partial coloring can be completed to a total proper coloring of the graph”

Does that make you

I hope it does, because otherwise it would imply I have a bad taste in exciting math problems. Anyway, back to work.

_______________________________

A regular graph is one in which the degree of each vertex ( i.e. the number of vertices it is connected to)  is the same. Any n^2*n^2 sudoku is a regular graph of degree 3n^2-2n-1

Now for the punchline – the theorems which answer our question. I will simply state the 2 brilliant theorems here. You can read their equally brilliant proofs in the original paper.

Theorem 1: Let G be a finite graph with v vertices. Let C be a partial colouring of t vertices of G using d_0 colours. Let p_{G,C}(\lambda) be the number of ways of completing this colouring by using \lambda colours to obtain a proper colouring. Then p_{G,C}(\lambda) is a monic polynomial in \lambda with integer coefficients of degree v-t for \lambda \geq d_0

Implications: The number of ways of completing our 9*9 sudoku is p_{G,C}(9). A unique solution is quaranteed if and only if p_{G,C}(9)=1.

____________________________________________

The minimal number of colours required to properly colour the vertices of a graph G is called the chromatic number of G and denoted \chi(G)

____________________________________________

Theorem 2: Let G b a graph with chromatic number \chi(G) and C be a partial colouring of G using only \chi(G)-2 colours. If the partial coloring can be completed to a total proper coloring of G, then there are at least two ways of extending the colouring.

Implications: If C is a partial colouring of G that can be uniquely completed to a proper total colouring, then C must use at least \chi(G)-1 colours. So for our 9*9 sudoku, at least 8 colours must be used in the given cells for the sudoku to be “well formed”

Note that with these theorems you can make statements about sudokus of all sizes!

____________________________________________

References:

Categories: Math Tags: , ,

Discrete Quantum Gravity

October 19, 2011 1 comment

Stanley Gudder, University of Denver

Q. GR deals with smooth functions on spacetime. QM deals with self adjoint operators on a Hilbert space. How are they related?

A. GR and QM both have bad singularities. Maybe we shouldn’t be looking at the continuum but the discrete picture!

We discuss the causal set approach to unify gravity and quantum mechanics. Let us begin with light cones. We know about the future and past lightcones of an event, say a.

Source: Wikipedia

Introduction and definitions


We talk about the causal structure (M,<) of a Lorentzian spacetime (M,g) . M is a partially ordered set(Poset).

For a, b \in M, we say a< b if b is in the causal future of a.

In the discrete situation, the smallest length is the Planck length l_p \sim 1.6 \times 10^{-35} and the smallest time interval is l_t \sim 5.4 \times 10^{-43}

We call a finite poset a ‘causet

\mathbb{P}_m = All causets of cardinality m.

\mathbb{P} = \bigcup_m \mathbb{P}_m

If a<b , we call a the ancestor and b the successor.

If a<b, we call a the parent and b the child if
!\exists c \ni a<b<c

a is maximal if !\exists b \ni a<b

X \in \mathbb{P}_m, Y \in \mathbb{P}_{m+1}

X produces Y if Y is obtained from X by adjoining a single element to X that is maximal in Y. We call X the producer and Y the offspring.

A path in \mathbb{P} is a string
\omega= \omega_1 \omega_2 \ldots \ni \omega_i \in \mathbb{P}_i, \omega_{i+1} \in \mathbb{P}_{i+1}

Each such path represents a ‘universe’. Every l_t unit of time we have a new element in the path. Note that we have 2 notions of time here, the ‘chronological time’ and the ‘geometric time’.

An n-path is
\omega= \omega_1 \omega_2 \ldots \omega_n

\Omega = \{\omega|\omega= \omega_1 \omega_2 \ldots \}

\Omega_n = \{\omega|\omega= \omega_1 \omega_2 \ldots \omega_n \}

Cylinder(\omega_0) = \{\omega \in \Omega| \omega= \omega_0 \ldots\}

For A \subseteq \Omega_n,  cyl(A)= \bigcup_{\omega \in A} cyl(\omega)

a_n = \{cyl(A): A \subseteq \Omega_n\}

We have the heirarchy
a_1 \subseteq a_2 \subseteq a_3\subseteq \ldots

C(\Omega) = \bigcup a_n. This is an algebra of the subsets of \Omega.

If X \rightarrow Y in r isomorphic ways,
we write m(X \rightarrow Y) = r, where m is the multiplicity.

Source: DQG by Stan Gudder

Classical Sequential Growth Processes

C= (C_0, C_1, \ldots)
C_i \geq 0 are the coupling constants.

For r\leq s \in \mathbb{N} define
\lambda_c(s,r) = \displaystyle\sum\limits_{k=0}^s \begin{pmatrix} s-r\\k-r\end{pmatrix} C_k

X \in \mathbb{P}_m, Y \in \mathbb{P}_{m+1}, X \rightarrow Y

We define the transition probability as

p_c(X \rightarrow Y) = m(X \rightarrow Y) \frac{\lambda_c(\alpha, \pi)}{\lambda_c(m, 0}

where
\alpha is the number of ancestors
\pi is the number of elements adjoined to X to get Y.

It is not obvious that this is a probability but this can be shown.

For the part of the talk from here onward, I will just sketch the outline here. We can define a corresponding quantum sequential growth process which leads to a theory of quantum gravity. I would encourage interested reader to read the original papers listed below.

Further readings and references-