combinatorics « On the learning curve…

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 ${\Delta_{u}(d,n)}$ of a ${d}$ dimensional polyhedron with ${n}$ facets has known upper and lower bounds.

${n-d+\lfloor d/5 \rfloor \le \Delta_{u}(d,n) \le n^{\log d +1}}$ .

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 ${\Delta_{u}(d,n) \le \Omega\left(n^{3/2}\right)}$ if ${d}$ is allowed to grow with ${n}$ .

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 ${\mathcal{B}_{d,n}}$ .The largest diameter of a graph in ${\mathcal{B}_{d,n}}$ is denoted by ${D(d,n)}$ . They find that, ${D(d,n) =\Omega\left(n^{3/2}\right)}$ and then using the fact that ${\Delta_{u}(d,n) \le D(d,n)}$ , they conclude the bound ${\Delta_{u}(d,n) \le \Omega\left(n^{3/2}\right)}$

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 $3$ variables over all variables such that, the sum of the index variables always equal to a constant $n$ .

$\displaystyle \sum_{\underset{i+j+k=n}{i,j,k}}f(i,j,k)$

Clearly, the indices here runs over all the ordered partitions of the number $3$ . Since $3$ 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 $n$ by $P(n)$ and $Q(n)$ respectively.

$Q(3) =( (3), (2, 1),(1, 1, 1))$ . The ordered partition will have the permutations of each of these on the three positions! So $(0,0,3)$ and $(0,3,0)$ are different sets of $P(3)$ whereas, they are considered as one $(3)$ in $Q(3)$ . The summation needs to be carried over the ordered partition list $P(n)$ . Since both $Q(n)$ and $P(n)$ grow pretty big with even modest $n$ , 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:

$\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }$

$\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1-n_2)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }$

typical values for $n$ is $20$ and $k$ is around $10$ . 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 $a_1$ and then scale it to get the requisite sum. It can be written as follows:

$\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }$

$=\frac{a_1}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \frac{\partial}{\partial a_1}\left[a_1 \left(a_1+a_2+\ldots+a_k\right)^{n}\right]$

$=\frac{a_1}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \left[n a_1 \left(a_1+a_2+\ldots+a_k\right)^{n-1}+\left(a_1+a_2+\ldots+a_k\right)^{n}\right]$

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:

$\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1-n_2)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }$

$=\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_1+1)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }$

$-\displaystyle \sum_{n_1+n_2+\ldots+n_k=n}{(n_2)a_1\frac{n!}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }$

$=\frac{a_1}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \frac{\partial}{\partial a_1}\left[a_1 \left(a_1+a_2+\ldots+a_k\right)^{n}\right]$

$-\frac{a_1 a_2}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \frac{\partial}{\partial a_2}\left[\left(a_1+a_2+\ldots+a_k\right)^{n}\right]$

$=\frac{a_1}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \left[n a_1 \left(a_1+a_2+\ldots+a_k\right)^{n-1}+\left(a_1+a_2+\ldots+a_k\right)^{n}\right]$

$-\frac{a_1 a_2}{{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}}} \left[n \left(a_1+a_2+\ldots+a_k\right)^{n-1}\right]$

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

$\displaystyle \sum_{\sum_{j}{ n_j}=n}{\frac{n!(n_1+1)a_1}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }=\frac{a_1\left(na_1+\sum_{i}{a_i}\right)}{{\left(\sum_{i=1}^{k}{a_i}\right)^{2}}}$

$\displaystyle \sum_{\sum_{j}{ n_j}=n}{\frac{n!(n_1+1-n_2)a_1}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }=\frac{a_1\left(n(a_1-a_2) +\sum_{i}{a_i}\right)}{{\left(\sum_{i=1}^{k}{a_i}\right)^{2}}}$

$\displaystyle \sum_{\sum_{j}{ n_j}=n}{\frac{n!(n_l)a_1}{n_1!n_2!\ldots n_k!}\frac{a_{1}^{n_1} a_{2}^{n_2} \ldots a_{k}^{n_k}}{\left(\sum_{i=1}^{k}{a_i}\right)^{n+1}} }=\frac{a_1 a_l n}{{\left(\sum_{i=1}^{k}{a_i}\right)^{2}}}$

	alpsholic on Thomas Cover (1938-2012)
	Raghavendra.T.R on Sanskrit as a computer la…
	Ram on Yesudas and Rafi singing same…
	Dirk D. Anderson on Sanskrit as a computer la…
	Karthik on End of an Era: Steve Jobs.…

M	T	W	T	F	S	S
« Mar
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

Tag Archive

Diameter of Polyhedra:some bounds

Summation over multiple variables

Recent Comments

Recent Posts

Top Clicks

Pages

Archives

Categories

Blogroll

Meta

Tags

Follow “On the learning curve...”