You are currently browsing the tag archive for the ‘combinatorics’ tag.

Todays IPG seminar had Fritz Eisenbrand (the Disctete Opt chair, Math department EPFL) talking about Diameter of Polyhedra:Limits of Abstraction. I don’t think I followed the topic too well, but this is a share of what I understood.

The topic is about a convex geometric problem on the diameter of a polyhedra. The question of whether the diameter of a polyhedron is polynomial or not seemed to be a longstanding open problem. The largest diameter of a dimensional polyhedron with facets has known upper and lower bounds.

.

The lower bound is due to Klee and Walkup and upper bound to Kalai and Kleitman. These bounds also hold good for combinatorial abstractions of the 1-skeleton of non-degenerate polyhedra (Polyhedron here is called non-degenrate). What Fritz and his colleagues have done is to look into the gap between these known lower and upper bounds. Apparently, the gap is wide and they have made some progress to get a super linear lower bound if is allowed to grow with .

The way they showed this bound is by establishing the bound for the largest diemeter of a graph in a base abstraction family. Let us say, the abstraction family of connected graphs be denoted by .The largest diameter of a graph in is denoted by . They find that, and then using the fact that , they conclude the bound

I have not had a chance to see their paper yet. I must say, the proof was not all that within my grab during the talk. However it appeared that it is based on some layering and combinatorics. He said some applications to covering problem, in particular disjoint covering design which I didn’t follow that well. Sometimes I get the feeling that I am a little dumb to grasp these ideas during a talk. I wonder whether others understand it very well on a first shot presentation. I have put it in my agenda (among the millions of other papers to read) to see through this problem and proof, one day! His presentation was very clear and legible though.

I am caught with a little trouble to figure out an easier way to set up and solve a summation of a function of several variables. I just realized that Mathematica doesnt allow me to add a constraint in the summation operation. My problem is that, the summation should be performed over the ordered partition set of a number.

An example, will illustrate the problem definition a lot better. Suppose I want to compute the sum of a function of variables over all variables such that, the sum of the index variables always equal to a constant .

Clearly, the indices here runs over all the ordered partitions of the number . Since is not that big a number, we can simply write these partitions by hand and somehow get the job done. Let us say denote the ordered partitions and unordered partitions of the number by and respectively.

. The ordered partition will have the permutations of each of these on the three positions! So and are different sets of whereas, they are considered as one in . The summation needs to be carried over the ordered partition list . Since both and grow pretty big with even modest , the job of manual summation is not that appealing. I really hoped mathematica to aid me here. Unfortunately, I don’t see a way out here, other than the painful individual partition sum. Anyway, for the curious reader, the sum I attempt are of the following types:

typical values for is and is around . If any enthused reader finds a way/trick, I will be happy to sponsor a coffee 🙂 (Sorry at this recession time, nothing more 😦 sadly…).

In fact, the first one is easy (Interestingly, I just found a way, while typesetting the blog). I can do a differential with respect to and then scale it to get the requisite sum. It can be written as follows:

Second one is the trouble maker 😦

Oh man! power of a coffee. As I am typing this on a moody Lausanne swiss weather, here comes the trick. I just made a coffee and that seemed to have worked. I guess I can apply a similar trick to the second one too. Basically, we can split them into two expressions and then write each as differential versions of a multinomial sum. Here it is:

Amazingly, we can simplify both to get a simple looking expression. I am glad! Here is what I finally got:

## Recent Comments