Today’s post is about the following paper, a joint work with Qiuyi Zhang, one of my advisees. Qiuyi Zhang is now a graduate student in the Mathematics department of Berkeley.
- Shiva Kintali, Qiuyi Zhang. Forbidden Directed Minors and Directed Pathwidth. (Preprint is available on my publications page)
Undirected graphs of pathwidth at most one are characterized by two forbidden minors i.e., (i) the complete graph on three vertices and (ii) the spider graph with three legs of length two each (see the following figure).
Directed pathwidth is a natural generalization of pathwidth to digraphs. We proved that digraphs of directed pathwidth at most one are characterized by a finite number of forbidden directed minors. In particular, we proved that the number of vertices in any forbidden directed minor is at most 8*160000+7. Ahem !!
This paper falls in the “directed minors” part of my research interests. In an earlier theorem, proved in April 2013 (see this earlier post), we proved that partial 1-DAGs are characterized by three forbidden directed minors. In a similar vein, I conjectured that the digraphs with directed pathwidth at most 1 are characterized by a finite number of forbidden directed minors. I assumed that the number of forbidden directed minors is number is around 100. So we started this project in May 2013 and started making a list of carefully constructed forbidden directed minors and tried to extend our techniques from partial 1-DAGs. Here is an initial list of minors we found.
All the forbidden minors we found, looked very cute and we assumed that a proof is nigh. Soon, we realized that the list is growing quickly and none of our earlier techniques are applicable. After almost an year of patient efforts and roller coaster rides, we proved our finiteness theorem in May 2014, two weeks before Qiuyi Zhang’s thesis defense. It took us 10 more months to get the paper to its current status. So this is a two year long adventure.
I am hoping to prove more theorems in the “directed minors” area in the coming years. The current paper taught me that patience and focus are big factors to make consistent progress. There should be a nice balance between `proving new theorems’ and `writing up the existing results’.
This is a short post about the following paper in my directed minor series :
- Shiva Kintali. “Directed Minors III. Directed Linked Decompositions“. Preprint available on my publications page.
Thomas [Tho’90] proved that every undirected graph admits a linked tree decomposition of width equal to its treewidth. This theorem is a key technical tool for proving that every set of bounded treewidth graphs is well-quasi-ordered. An analogous theorem for branch-width was proved by Geelen, Gerards and Whittle [GGW’02]. They used this result to prove that all matroids representable over a fixed finite field and with bounded branch-width are well-quasi-ordered under minors. Kim and Seymour [KS’12] proved that every semi-complete digraph admits a linked directed path decomposition of width equal to its directed pathwidth. They used this result to show that all semi-complete digraphs are well-quasi-ordered under “strong” minors.
In this paper, we generalize Thomas’s theorem to all digraphs.
Theorem : Every digraph G admits a linked directed path decomposition and a linked DAG decomposition of width equal to its directed pathwidth and DAG-width respectively.
The above theorem is crucial to prove well-quasi-ordering of some interesting classes of digraphs. I will release Directed Minors IV soon. Stay tuned !!
This is a short post about the following paper :
- Shiva Kintali. “Directed Width Parameters and Circumference of Digraphs“. Preprint available on my publications page.
We prove that the directed treewidth, DAG-width and Kelly-width of a digraph are bounded above by its circumference plus one. This generalizes a theorem of Birmele stating that the treewidth of an undirected graph is at most its circumference.
Theorem : Let G be a digraph of circumference l. Then the directed treewidth, DAG-width and Kelly-width of G are at most l + 1.
The above theorem can be seen as a mini mini mini directed grid minor theorem. I will be using this theorem in future papers to make progress towards a directed grid minor theorem. Stay tuned !!
Today’s post is about the following paper, a joint work with Qiuyi Zhang, one of my advisees. Qiuyi Zhang is an undergraduate (rising senior) in our mathematics department.
- Shiva Kintali, Qiuyi Zhang. Forbidden Directed Minors and Kelly-width. (Preprint available on my publications page)
It is well-known that an undirected graph is a partial 1-tree (i.e., a forest) if and only if it has no minor. We generalized this characterization to partial 1-DAGs. We proved that partial 1-DAGs are characterized by three forbidden directed minors, and , shown in the following figure. We named the last two graphs as and because their bidirected edges resemble the letters N and M.
Partial k-trees characterize bounded treewidth graphs. Similarly, partial k-DAGs characterize bounded Kelly-width digraphs. Kelly-width is the best known generalization of treewidth to digraphs.
As mentioned in the paper, I have a series of upcoming papers (called Directed Minors) making progress towards a directed graph minor theorem (i.e., all digraphs are well-quasi-ordered by the directed minor relation). For more details of the directed minor relation, read the current paper. I will post about the upcoming results as and when the preprints are ready.
One year back (on 6/6/12) I announced a beta version of TrueShelf, a social-network for sharing exercises and puzzles especially in mathematics and computer science. After an year of testing and adding new features, now I can say that TrueShelf is out of beta.
TrueShelf turned out to be a very useful website. When students ask me for practice problems (or books) on a particular topic, I simply point them to trueshelf and tell them the tags related to that topic. When I am advising students on research projects, I first tell them to solve all related problems (in the first couple of weeks) to prepare them to read research papers.
Here are the features in TrueShelf 1.0.
- Post an exercise (or) multiple-choice question (or) video (or) notes.
- Solve any multiple-choice question directly on the website.
- Add topic and tags to any post
- Add source or level (high-school/undergraduate/graduate/research).
- Show text-books related to a post
- Show related posts for every post.
- View printable version (or) LaTex version of any post.
- Email / Tweet / share on facebook (or) Google+ any post directly from the post.
- Add any post to your Favorites
- Like (a.k.a upvote) any post.
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+. Here is a screenshot highlighting the important features.
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.