Graceful Diameter-6 Trees

Graceful Tree Conjecture is one of my favorite open problems (See this earlier post). Trees with diameter 4 and 5 are known to be graceful a decade ago.

One of my advisees, Matt Superdock, made progress towards proving that all diameter 6 trees are graceful. Matt is an undergraduate senior in our Mathematics Department. He proved that an interesting class of diameter 6 trees are graceful. His thesis is available here.

I hope his work motivates more researchers to make progress towards resolving Graceful Tree Conjecture, particularly for diameter 6 trees. Matt’s work really tests the limit of current techniques. Perhaps we need new techniques/insights to prove that all diameter 6 trees are graceful.

 

 

 

Advertisements

Happy Birthday Paul Erdos

Today (March 26 2013) is the 100th Birthday of Paul Erdos. The title of my Blog is inspired by one of his famous sayings “My Brain is Open”. In one of my earlier posts I mentioned a book titled “The Man Who Loved Only Numbers” about his biography.

Paul Erdos published more than 1500 papers. Most of them left a legacy of open problems and conjectures. What is your favorite open problem from Erdos’s papers ? Leave a comment. Hope we can solve some of his open problems during this special year.

Here are some interesting links :

If you know any interesting Erdos links, leave a comment.

Here is a painting of Paul Erdos, I made couple years back.

paul_erdos_painting

Open Problems from Lovasz and Plummer’s Matching Theory Book

I always have exactly one bed-time mathematical book to read (for an hour) before going to sleep. It helps me learn new concepts and hopefully stumble upon interesting open problems. Matching Theory by Laszlo Lovasz and Michael D. Plummer has been my bed-time book for the last six months. I bought this book 3 years back (during my PhD days) but never got a chance to read it. This book often disappears from Amazon’s stock. I guess they are printing it on-demand.

If you are interested in learning the algorithmic and combinatorial foundations of Matching Theory (with a historic perspective), then this book is a must read. Today’s post is about the open problems mentioned in Matching Theory book. If you know the status (or progress) of these problems, please leave a comment.

—————————————————————————-

1 . Consistent Labeling and Maximum Flow 

Conjecture (Fulkerson) : Any consistent labelling procedure results in a maximum flow in polynomial number of steps.

—————————————————————————-

2. Toughness and Hamiltonicity

The toughness of a graph G, t(G) is defined to be +\infty, if G = K_n and to be min(|S|/c(G-S)), if G \neq K_n. Here c(G-S) is the number of components of G-S.

Conjecture (Chvatal 1973) : There exists a positive real number t_0 such that for every graph G, t(G) \geq t_0 implies G is Hamiltonian.

—————————————————————————-

3. Perfect Matchings and Bipartite Graphs

Theorem : Let X be a set, X_1, \dots, X_t \subseteq X and suppose that |X_i| \leq r for i = 1, \dots, t. Let G be a bipartite graph such that

a) X \subseteq V(G),

b) G - X_i has a perfect matching , and

c) if any edge of G is deleted, property (b) fails to hold in the resulting graph.

Then, the number of vertices in G with degree \geq 3 is at most r^3 {t \choose 3}.

Conjecture : The conclusion of the above theorem holds for non-bipartite graphs as well.

—————————————————————————-

4. Number of Perfect Matchings

Conjecture (Schrijver and W.G.Valiant 1980) : Let \Phi(n,k) denote the minimum number of perfect matchings a k-regular bipartite graph on 2n points can have. Then, \lim_{n \to \infty} (\Phi(n,k))^{\frac{1}{n}} = \frac{(k-1)^{k-1}}{k^{k-2}}.

—————————————————————————-

5. Elementary Graphs

Conjecture : For k \geq 3 there exist constants c_1(k) > 1 and c_2(k) > 0 such that every k-regular elementary graph on 2n vertices, without forbidden edges , contains at least c_2(k){\cdot}c_1(k)^n perfect matchings. Furthermore c_1(k) \to \infty as k \to \infty.

—————————————————————————-

6. Number of colorations

Conjecture (Schrijver’83) : Let G be a k-regular bipartite graph on 2n vertices. Then the number of colorings of the edges of G with k given colors is at least (\frac{(k!)^2}{k^k})^n.

—————————————————————————-

7. The Strong Perfect Graph Conjecture (resolved)

Theorem : A graph is perfect if and only if it does not contain, as an induced subgraph, an odd hole or an odd antihole.

—————————————————————————-

TrueShelf

I have been teaching (courses related to algorithms and complexity) for the past six years (five years as a PhD student at GeorgiaTech, and the past one year at Princeton). One of the most challenging and interesting part of teaching is creating new exercises to help teach the important concepts in an efficient way. We often need lots of problems to include in homeworks, midterms, final exams and also to create practice problem sets.

We do not get enough time to teach all the concepts in class because the number of hours/week is bounded. I personally like to teach only the main concepts in class and design good problem sets so that students can learn the generalizations or extensions of the concepts by solving problems hands-on. This helps them develop their own intuitions about the concepts.

Whenever I need a new exercise I hardly open a physical textbook. I usually search on internet and find exercises from a course website (or) “extract” an exercise from a research paper. There are hundreds of exercises “hidden” in pdf files across several course homepages. Instructors often spend lots of time designing them. If these exercises can reach all the instructors and students across the world in an efficiently-indexed form, that will help everybody. Instructors will be happy that the exercises they designed are not confined to just one course. Students will have an excellent supply of exercises to hone their problem-solving skills.

During 2008, half-way through my PhD, I started collected the exercises I like in a private blog. At the same time I registered the domain trueshelf.com to make these exercises public. In 2011, towards the end of my PhD, I started using the trueshelf.com domain and made a public blog so that anybody can post an exercise. [ Notice that I did not use the trueshelf.com domain for three years. During these three years I got several offers ranging upto $5000 to sell the domain. So I knew I got the right name 🙂 ] Soon, I realized that wordpress is somewhat “static” in nature and does not have enough “social” features I wanted. A screenshot of the old website is shown below.

The new version of TrueShelf is a social website enabling “crowd-sourcing” of exercises in any area. Here is the new logo, I am excited about 🙂

The goal of TrueShelf is to aid both the instructors and students by presenting quality exercises with tag-based indexing. Read the TrueShelf FAQ for more details. Note that we DO NOT allow users to post solutions. Each user may add his own “private” solution and notes to any exercise. I am planning to add more features soon.

In the long-run, I see TrueShelf becoming a “Youtube for exercises”. Users will be able to create their own playlists of exercises (a.k.a problem sets) and will be recommended relevant exercises. Test-preparation agencies will be able to create their own channels to create sample tests.

Feel free to explore TrueShelf, contribute new exercises and let me know if you have any feedback (or) new features you want to see. You can also follow TrueShelf on facebook, twitter and google+.

Let’s see how TrueShelf evolves.

Computing Bounded Path Decompositions in Logspace

Today’s post is a continuation of earlier posts (here, here, here, here) on graph isomorphism, treewidth and pathwidth. As mentioned earlier, the best known upper bound for Graph Isomorphism of partial k-trees is LogCFL.

Theorem ([Das, Toran and Wagner’10]) : Graph isomorphism of bounded treewidth graphs is in LogCFL.

One of the bottlenecks of the algorithm of [DTW’10] is computing bounded tree decompositions in logspace. This is recently resolved by an amazing result of Elberfeld, Jakoby and Tantau [EJT’10]. The results in this paper are very powerful. Unfortunately, it is still not clear how to improve the LogCFL upper bound.

Can we improve the upper bound for special cases of partial k-trees ? How about bounded pathwidth graphs ? Again, one bottleneck here is to compute bounded path decompositions in logspace. [EJT’10]’s paper does not address this bottleneck and it is not clear how to extend their algorithm to compute path decompositions.

In joint work with Sinziana Munteanu, we resolved this bottleneck and proved the following theorem. Sinziana is a senior undergraduate student in our department. She is working with me on her senior thesis.

Theorem (Kintali, Munteanu’12) : For all constants k, l \geq 1, there exists a logspace algorithm that, when given a graph G of treewidth \leq l, decides whether the pathwidth of G is at most k, and if so, finds a path decomposition of G of width \leq k in logspace.

A draft of our results is available here. The above theorem is a logspace counterpart of the corresponding polynomial-time algorithm of [Bodlaender, Kloks’96]. Converting it into a logspace algorithm turned out to be a tedious task with some interesting tricks. Our work motivates the following open problem :

Open problem : What is the complexity of Graph Isomorphism of bounded pathwidth graphs ? Is there a logspace algorithm ?

Stay tuned for more papers related to graph isomorphism, treewidth and pathwidth. I am going through a phase of life, where I have more results than I can type. Is there an app that converts voice to latex ? Is there a journal that accepts hand-written proofs ? 🙂

Complexity of Tessel

One of my hobbies (I developed during my PhD) is designing boardgames. I designed three boardgames so far, one of which is Tessel, a word-building game based on graph theory. I am glad that Tessel is getting good feedback especially from schools and families. One of the most time-consuming part of Tessel’s design is deciding what values to assign to the letters and deciding which pairs of letters to use in the tiles. The pairs of letters are carefully chosen based on computer simulations of frequency of letters in english words and their “relative” importance. The pairs are chosen so as to give fair share to both vocabulary skills and optimization skills.

Today’s post is about a nice theoretical problem arising from this game.

Before you read further, please read the rules of Tessel. Henceforth I will assume that you understood the rules and goal of this game.

I guess you observed that the tiles are being placed on the edges of a planar graph. Tessel uses a special planar graph that has cycles of length 3,4,5 and 6. In general, this game can be played on any planar graph. I am planning to design another board using Cairo tessellation. Anyways, here is a theoretical problem :

Let S be a set of finite alphabets. You are given two different words (using alphabets from S) of length l1 and l2. Construct a planar graph G and label each edge with two alphabets, such that there are two walks in G that correspond to the given two words. (Read the rules of tessel  and look at these examples to understand this correspondence). Your goal is to construct G with minimum number of vertices (or minimum number of edges).

In general you can ask the above question given k different words. What is the complexity of this problem ? I don’t know. I haven’t given it a deep thought. These days whatever I do for fun (to take my mind off open problems), ends up in another open problem 😦