combinatorics

by

Open problems for 2014

Wish you all a Very Happy New Year. Here is a list of my 10 favorite open problems for 2014. They belong to several research areas inside discrete mathematics and theoretical computer science. Some of them are baby steps towards resolving much bigger open problems. May this new year shed new light on these open problems.

  • 2. Optimization : Improve the approximation factor for the undirected graphic TSP. The best known bound is 7/5 by Sebo and Vygen.
  • 3. Algorithms : Prove that the tree-width of a planar graph can be computed in polynomial time (or) is NP-complete.
  • 4. Fixed-parameter tractability : Treewidth and Pathwidth are known to be fixed-parameter tractable. Are directed treewidth/DAG-width/Kelly-width (generalizations  of  treewidth) and directed pathwidth (a generalization of pathwidth) fixed-parameter tractable ? This is a very important problem to understand the algorithmic and structural differences between undirected and directed width parameters.
  • 5. Space complexity : Is Planar ST-connectvity in logspace ? This is perhaps the most natural special case of the NL vs L problem. Planar ST-connectivity is known to be in UL \cap coUL. Recently, Imai, Nakagawa, Pavan, Vinodchandran and Watanabe proved that it can be solved simultaneously in polynomial time and approximately O(√n) space.
  • 6. Metric embedding : Is the minor-free embedding conjecture true for partial 3-trees (graphs of treewidth 3) ? Minor-free conjecture states that “every minor-free graph can be embedded in l_1 with constant distortion. The special case of planar graphs also seems very difficult. I think the special case of partial 3-trees is a very interesting baby step.
  • 7. Structural graph theory : Characterize pfaffians of tree-width at most 3 (i.e., partial 3-trees). It is a long-standing open problem to give a nice characterization of pfaffians and design a polynomial time algorithm to decide if an input graph is a pfaffian. The special of partial 3-trees is an interesting baby step.
  • 8. Structural graph theory : Prove that every minimal brick has at least four vertices of degree three. Bricks and braces are defined to better understand pfaffians. The characterization of pfaffian braces is known (more generally characterization of bipartite pfaffians is known). To understand pfaffians, it is important to understand the structure of bricks. Norine,Thomas proved that every minimal brick has at least three vertices of degree three and conjectured that every minimal brick has at least cn vertices of degree three.
  • 9. Communication Complexity : Improve bounds for the log-rank conjecture. The best known bound is O(\sqrt{rank})
  • 10. Approximation algorithms : Improve the approximation factor for the uniform sparsest cut problem. The best known factor is O(\sqrt{logn}).

Here are my conjectures for 2014 🙂

  • Weak Conjecture : at least one of the above 10 problems will be resolved in 2014.
  • Conjecture : at least five of the above 10 problems will be resolved in 2014.
  • Strong Conjecture : All of the above 10 problems will be resolved in 2014.

Have fun !!

by

TrueShelf 1.0

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.

trueshelf

by

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

by

Recreational Math Books – Part I

Most of us encounter math puzzles during high-school. If you are really obsessed with puzzles, actively searching and solving them, you will very soon run out of puzzles !! One day you will simply realize that you are not encountering any new puzzles. No more new puzzles. Poof. They are all gone. You feel like screaming “Give me a new puzzle“. This happened to me around the end of my undergrad days. During this phase of searching for puzzles, I encountered Graceful Tree Conjecture and realized that there are lots of long-standing open “puzzles”. I don’t scream anymore. Well… sometimes I do scream when my proofs collapse. But that’s a different kind of screaming.

Sometimes, I do try to create new puzzles. Most of the puzzles I create are either very trivial to solve (or) very hard and related to long-standing conjectures. Often it takes lots of effort and ingenuity to create a puzzle with right level of difficulty.

In today’s post, I want to point you to some of the basic puzzle books that everybody should read. So, the next time you see a kid screaming “Give me a new puzzle“, simply point him/her to these books. Hopefully they will stop screaming for sometime. If they comeback to you soon, point them to Graceful Tree Conjecture  🙂

1) Mathematical Puzzles: A Connoisseur’s Collection by Peter Winkler

2) Mathematical Mind-Benders by Peter Winkler

3) The Art of Mathematics: Coffee Time in Memphis by Bela Bollobás

4) Combinatorial Problems and Exercises by Laszlo Lovasz

5) Algorithmic Puzzles by Anany Levitin and Maria Levitin

I will mention more recreational math books in part 2 of this blog post.

by

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.

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

by

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.

by

Kriesell’s Conjecture

Today’s short post is about Kriesell’s conjecture. In my first year of PhD I enjoyed reading several papers related to this cute conjecture.

Nash-Williams [N’61] and Tutte [Tutte’61] independently proved that a graph G(V,E) has k edge-disjoint spanning trees if and only if E(P) \geq k(|P|-1) for every partition P of V into non-empty classes, where E(P) denotes the number of edges connecting distinct classes of P. One interesting corollary of this result is the following :

Theorem : Every 2k-edge-connected graph has k edge-disjoint spanning trees.

Let G(V,E) be an undirected multigraph and S \subseteq V. An S-tree is a tree of G that contains every vertex in S. An S-cut is a subset of edges whose removal disconnects some vertices in S. A graph is k-S-connected if every S-cut has at least k edges. Kriesell conjectured the following generalization of the above theorem.

Kriesell’s conjecture : If G is 2k-S-connected, then G has k edge-disjoint S-trees.

The first breakthrough towards proving Kriesell’s conjecture was by Lau. He proved that if G is 24k-edge-connected in T then it has k edge-disjoint Steiner trees. Recently, West and Wu [pdf] proved that it suffices for S to be 6.5k-edge-connected in G.

Open Problems

  1. Obvious open problem is to prove or disprove Kriesell’s conjecture.
  2. There a several related open problems about S-connectors in West-Wu’s paper.

References :

  • [Tutte’61] W.T.Tutte : On the problem of decomposing a graph into n connected factors, J. London Math. Soc. 36 (1961), 221–230.
  • [N’61] C.St.J.A.Nash-Williams : Edge disjoint spanning trees of finite graphs, J. London Math. Soc. 36 (1961), 445–450.
  • [Lau’07] L. C. Lau : An approximate max-Steiner-tree-packing min-Steiner-cut theorem. Combinatorica 27 (2007), 71–90

			

	
	



			
				



	
	


		
					

				 by 			

				
Open Problems from FOCS 2009

	


		

		
Here are some open problems (that interest me) from FOCS 2009. If you want to share an open problem, please leave a comment.


Starting with my paper…….


1) Reducibility Among Fractional Stability Problems [pdf]




Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram and Shang-Hua Teng.


Summary : We resolve the computational complexity of a number of outstanding open problems with practical applications and introduce a simple PPAD-complete game (the preference game). Here is the list of problems we show to be PPAD-complete, along with the domains of practical significance:  1) Fractional Stable Paths Problem (FSPP) – Internet routing;  2) Core of Balanced Games – Economics and Game theory;  3) Scarf’s Lemma – Combinatorics;  4) Hypergraph Matching – Social Choice and Preference Systems;  5) Fractional Bounded Budget Connection Games (FBBC) – Social networks; and 6) Strong Fractional Kernel – Graph Theory.


 Open Problems : The complexity of Discrete Ham Sandwich Problem and Necklace Splitting Problem are open. These are shown to be in PPAD by Papadimitiou in 1994.


2) Linear systems over composite moduli [pdf]


Arkadev Chattopadhyay and Avi Wigderson.


 Summary and Open Problems : Dick Lipton already summarized their result along with open problems.


3) Regularity Lemmas and Combinatorial Algorithms [pdf]


Nikhil Bansal, Ryan Williams


 Summary : This paper presents new combinatorial algorithms for Boolean matrix multiplication (BMM) and preprocessing a graph to answer independent set queries. The authors give the first asymptotic improvements on “combinatorial” algorithms for dense BMM in many years, improving on the Four Russians O(n^3/(log^{2}n)) bound. Their use of Triangle removal lemma and Regularity lemma are particularly interesting.


Open Problems : Ryan mentioned the following open problems in his talk : (1) Can one construct a Weak Regular partition in O(n^{2.9}) time, deterministically ? (2) Can their techniques be applied to All Pairs Shortest Paths Problems ? (3) is there a Regularity concept that is better suited for Matrix Multiplication ?


4) Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP [pdf]



Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Howard Karloff


 Summary : They give a factor 1.990283 approximation algorithm for Prize-collecting TSP. This is the first result to break the barrier of 2 improving the primal-dual algorithm  of Goemans and Williamson. Recently Goemans, presented a 1.91457-approximation algorithm for the prize-collecting travelling salesman problem.


Open Problem : Obvious open problem is to improve this approximation factor.


5) Blackbox Polynomial Identity Testing for Depth 3 Circuits [pdf]


 Neeraj Kayal and Shubhangi Saraf. 


Open Problems : This paper has a well-written open problems section with specific open problems. If you are interested in polynomial identity testing, I encourage you to read them.