Second post about my summer research. This is a jump from the last one, but I need to clear my head. Here it goes.
After about two weeks of lots of reading, I've begun my independent inquiries. This will (and has to, to some extent) sound like pure brain-storming, incoherent babbling; but I need to keep track of where I want to get to.
We know (cite here) that the $h$-vector of a nestohedron $P_{\mathcal{B}}$ can be described in as the generating function of the descent number of its $\mathcal{B}$-trees:
$$h_{P_{\mathcal{B}}}(t) = \sum_T t^{\text{des}(T)}.$$
Given how there exists a bijection (cite here) between the vertices of $P_{\mathcal{B}}$, the $\mathcal{B}$-permutations and the $\mathcal{B}$-trees, it is clear that to understand the combinatorial structure of a nestohedra, we must understand the structure of its underlying building set.
In the case of graph-associahedra, I want to find results about their $h$- and $\gamma$-polynomials in constructive and intuitive ways. I've started working on finding that information about the graph-associahedra $P_{\mathcal{B}(\text{Cycle}_n)}$ of the cycle graph on $n$ vertices.
Let's suppose that we fully know what's the combinatorial structure of $P_{\mathcal{B}(\text{Path}_n)}$ (we do), and that we don't know anything about $P_{\mathcal{B}(\text{Cycle}_n)}$ (we do as well, but bare with me). If you consider the graph $\text{Path}_{(n-1)}$ with two added edges, from endpoints $1$ and $(n-1)$ to a new vertex $r$, you've essentially pictured $\text{Cycle}_n$ in your head. The idea of describing the graph-associahedra of the cycle graph in terms of the simpler path graph is cool. In fact, the idea of describing the graph-associahedra of any graph by `gluing' smaller, more understandable (or more understood) graphs is extremely attractive and logical to me. It makes sense to reuse simple constructs to provide descriptions of more complex ideas; but of course, it isn't easy. I don't even know if I'll be able to finish the example presented here, but it is a good warm-up exercise for this poor soul's first attempt at providing novel insight, no matter how insignificant.
I was feeling like finishing the post here, but i realize i haven't actually delved into the complicated stuff, and i want to reach the point where i can't go further, and observe then where's the weakness, where's the limitation.
We can define the set of $\mathcal{B}$-trees for $\text{Cycle}_n$ as follows: for each $r \in [n]$, construct the set of trees of $\text{Path}_{(n-1)}$ such that the label $i$ of every vertex of a tree $T$ is replaced by $i' = i + r \pmod{n}$. Join the root of $T$ to our newly defined root $r$, to get $T'$. Notice then that the forest of trees constructed from $\mathcal{B}(\text{Cycle}_n)$ has $n \cdot C_{(n-1)}$ trees ($C_n$ is the $n$th Catalan number; it is known that there are $C_n$ trees for the $n$-path).
So, to find $h_{P_{\mathcal{B}(\text{Cycle}_n)}}(t)$, we must count the descent numbers of the $n$ copies of the $\mathcal{B}$-forest of $\text{Path}_{(n-1)}$ with its labels shifted $r \in [n]$ modulo $n$. I hope you can see that the delicate part is the shifting of labels: if $n=5$ and in some tree from $\text{Path}_4$ we had a descent $4 \leftarrow 5$, when we adjoin the new root $r=1$, all indices are shifted and the descent becomes $5 \leftarrow 1$, which is not a descent anymore. Chaos! We must understand how does that shifting affect the descent number of the trees of $\text{Cycle}_n$. Here's where i'm at.
A small observation, to close this post. It may be obvious, but it has just occurred to me and i haven't come up with a proof from the top of my head: if you pick a tree $T$ from the forest of $\mathcal{B}(\text{Cycle}_n)$-trees, and exchange the root with its unique child, the resulting tree $T'$ is also a tree in the forest. If you apply the operation twice, you obviously go back to $T$. If closure were true, this would define an equivalence relation which halves the size of the forest. Postnikov et al. use a `similar' (this deserves triple quotes) operation to fully describe the graph-associahedra of the path graph. I may try to do something similar? But i realize that I'm not using what i know about the descents of the trees of the path graph itself! Back to work.
Thursday, July 9, 2015
Tuesday, June 30, 2015
Understanding convex polytopes (I)
This summer, i'm working in an intense month-long research program about discrete geometry (a.k.a. combinatorial geometry). To keep track of what i do, what i learn and what i don't, i'll be writing (hopefully) regular posts regarding the work i do through the day. That should help me a ton, and hopefully someone out there as well?
Consider a set of points $P \subset \mathbb{R}^n$. We say that $P$ is convex if for any $x,y \in P$, the segment $[x,y]$ is contained in $P$. An intersection of convex sets is convex, so we define the convex hull of $P$ as the smallest convex set that contains $P$:
$$\text{ConvexHull}(P) := \bigcap \{P' \subset \mathbb{R}^n : P \subset P', \text{ for $P'$ convex}\}$$
One of the fundamental concepts is that of a polytope: there are two equivalent definitions.
A $\mathcal{V}$-polytope is the convex hull of a finite set of points in $\mathbb{R}^n$.
An $\mathcal{H}$-polytope is the intersection of a finite set of closed halfspaces in $\mathbb{R}^n$ (that is; the region enclosed by a set of inequalities).
That these two definitions are equivalent is not trivial, but it has been proven, and it is not what I'm specially interested about.
What I'm interested in is the combinatorial structure of a given polytope (or family of polytopes). We compress all the combinatorial information of a polytope in three fundamental invariants: the $f$, $h$ and $\gamma$-vectors. The $f$-vector is defined as the vector $(f_0, f_1, ... , f_d)$, where $f_i$ denotes the amount of $i$-faces of $P$: $f_0$ is the amount vertices, $f_1$ the amount of edges, etc...
(TODO: $h$ and $\gamma$-vectors. Their relation to the $f$-vector.)
We define the $n$-simplex $\Delta^n$ as the convex hull of $\{e_i : i \in [1, ..., n]\}$, where $e_i$ is the $i$th standard basis vector of $\mathbb{R}^n$. Notice that $\Delta^n$ is affinely independent.
A $d$-polytope $P$ ($d$ dimensions) is simple if each of its vertices is incident to $d$ edges. A $d$-polytope is simplicial if all of its faces are simplices.
(TODO: More definitions, clearer exposition, give intuition. What a bad rhyme.)
Now we turn our attention to a particular way of constructing polytopes: from graphs. Consider a graph $G$ on the labeled vertices $[1, ..., n]$ which is connected (there is a path that connects any pair of vertices, but it needn't be direct). Define the connected building set as the set of all subsets of vertices of $G$, such that the induced subgraph is connected:
$$\mathcal{B}(G) := \{U \subset G : G|_U \text{ is connected}\}$$
The polytope derived from this is defined as the Minkowski sum
$$P_{\mathcal{B}(G)} = \sum_{U\in\mathcal{B}(G)} \Delta_U $$
of $U$-simplices $\Delta_U := ConvexHull(e_i : i \in U)$. We call $P$ a graph-associahedron, and in general, the $P_{\mathcal{B}}$ of some building set $\mathcal{B}$ is called the nestohedron.
It is obvious that the choice of graph will determine the resulting polytope. We will study the polytopes generated by particular kinds of graphs (cyclic, complete, path, stellar, etc...): particularly, we will work towards fully determining their combinatorial structure by finding the $f$, $h$ and $\gamma$ vectors.
Note we required $G$ to be connected, because disconnected elements (their simplex representation are points) have no effect on the Minkowski sum: a point added to anything is just a translation.
My doubts at the moment
So what I'm interested in understanding is how to combinatorially describe a graph-associahedra. The Minkowski sum of simplices gets hairy pretty quickly, and I feel like any insight into the structure of $P_{\mathcal{B}(G)}$ must come from the structure of $G$ itself. But how do I translate graph properties to geometric properties? I'll try to go over simple examples, and generalize from there.
Consider a set of points $P \subset \mathbb{R}^n$. We say that $P$ is convex if for any $x,y \in P$, the segment $[x,y]$ is contained in $P$. An intersection of convex sets is convex, so we define the convex hull of $P$ as the smallest convex set that contains $P$:
$$\text{ConvexHull}(P) := \bigcap \{P' \subset \mathbb{R}^n : P \subset P', \text{ for $P'$ convex}\}$$
One of the fundamental concepts is that of a polytope: there are two equivalent definitions.
A $\mathcal{V}$-polytope is the convex hull of a finite set of points in $\mathbb{R}^n$.
An $\mathcal{H}$-polytope is the intersection of a finite set of closed halfspaces in $\mathbb{R}^n$ (that is; the region enclosed by a set of inequalities).
That these two definitions are equivalent is not trivial, but it has been proven, and it is not what I'm specially interested about.
What I'm interested in is the combinatorial structure of a given polytope (or family of polytopes). We compress all the combinatorial information of a polytope in three fundamental invariants: the $f$, $h$ and $\gamma$-vectors. The $f$-vector is defined as the vector $(f_0, f_1, ... , f_d)$, where $f_i$ denotes the amount of $i$-faces of $P$: $f_0$ is the amount vertices, $f_1$ the amount of edges, etc...
(TODO: $h$ and $\gamma$-vectors. Their relation to the $f$-vector.)
We define the $n$-simplex $\Delta^n$ as the convex hull of $\{e_i : i \in [1, ..., n]\}$, where $e_i$ is the $i$th standard basis vector of $\mathbb{R}^n$. Notice that $\Delta^n$ is affinely independent.
A $d$-polytope $P$ ($d$ dimensions) is simple if each of its vertices is incident to $d$ edges. A $d$-polytope is simplicial if all of its faces are simplices.
(TODO: More definitions, clearer exposition, give intuition. What a bad rhyme.)
Now we turn our attention to a particular way of constructing polytopes: from graphs. Consider a graph $G$ on the labeled vertices $[1, ..., n]$ which is connected (there is a path that connects any pair of vertices, but it needn't be direct). Define the connected building set as the set of all subsets of vertices of $G$, such that the induced subgraph is connected:
$$\mathcal{B}(G) := \{U \subset G : G|_U \text{ is connected}\}$$
The polytope derived from this is defined as the Minkowski sum
$$P_{\mathcal{B}(G)} = \sum_{U\in\mathcal{B}(G)} \Delta_U $$
of $U$-simplices $\Delta_U := ConvexHull(e_i : i \in U)$. We call $P$ a graph-associahedron, and in general, the $P_{\mathcal{B}}$ of some building set $\mathcal{B}$ is called the nestohedron.
It is obvious that the choice of graph will determine the resulting polytope. We will study the polytopes generated by particular kinds of graphs (cyclic, complete, path, stellar, etc...): particularly, we will work towards fully determining their combinatorial structure by finding the $f$, $h$ and $\gamma$ vectors.
Note we required $G$ to be connected, because disconnected elements (their simplex representation are points) have no effect on the Minkowski sum: a point added to anything is just a translation.
My doubts at the moment
So what I'm interested in understanding is how to combinatorially describe a graph-associahedra. The Minkowski sum of simplices gets hairy pretty quickly, and I feel like any insight into the structure of $P_{\mathcal{B}(G)}$ must come from the structure of $G$ itself. But how do I translate graph properties to geometric properties? I'll try to go over simple examples, and generalize from there.
Monday, April 27, 2015
Quick trip to Madrid
Today i visited the Spanish capital for a few hours, with the objective of acquiring a USA student visa for my summer stay in Boston. After completing a few forms (in one of which i had to declare that, in fact, i have not killed anyone, trafficked with anyone, nor extorted, tortured or laundered money), waiting for my turn, and successfully completing a 1-minute Guiness World Record interview, i left just as i had arrived. With a perpetual cold.
Forgot to take pictures of Madrid itself. OUch. But here i post a pair of worthy ones that i took on my way back. There's an insane amount of wind turbines around there. Those would make nice album covers, don't you think?
I'm working on (ergo, reading + banging my head on) more mathematics, mainly. And thinking about next year's school research project, focusing again on artificial intelligence (with a more minimalist but general approach; think graphs).
Tuesday, March 31, 2015
On chinese cartoons
After reading exactly 0 pages of manga in the last two years, I somehow got caught up in Oyasumi Punpun. Not the most orthodox choice for a comeback, no the most sensible pick for a tranquil vacational noon.
I didn't know what I expected, and I haven't yet understood why did I even start reading in the first place. But wow, what a ride. I instantly fell in love with everything about it. The narrative, the dialogues... the artistic style is even coherent most of the time (yes, it's a bird, but don't sweat it; if you can't stand a human bird as a protagonist, what will you do when he becomes a pyramid?). I do certainly synchronize quite well with Punpun's initial vibrations, but it becomes harder as the storyline advances, until a point of disconnection (albeit not absolute; there's still a trace of us inside the late Punpun).
Not your pretty, light-hearted chinese cartoon, that is for sure. Sometimes, I asked myself whether it was a bit too pretentious or unnecessarily 'deep', but since everything made a bit of sense in my mind, I leave that for later thought. It's a fact that this work has surprised me far beyond my expectations, and I'm thankful for the... rollercoaster of 12+ hours it has provided me. I will come back to it and read it again someday, but thanks that's enough for today.
If you want to drift away from conventional manga, or are simply in search of something different that will hopefully talk to you more deeply, please consider Oyasumi Punpun. To paint it as a simple love story does not do it justice.
On an other note, it was Bach's birthday (31st of March in New Style date) and I had planned to record a performance of his fugue in E Major from the Well-Tempered Clavier II (BWV 878), but looks like he'll have to wait a bit more for my rendition. Chopin's C Major prelude (Op. 28) and C# minor étude (Op. 25) are on the works as well, but I'm just hopeful on the former.
Friday, February 13, 2015
Two little problems (ii)
Problem 2. Find the solutions of $x^6 + y^6 + z^6 = 6xyz - 3$.
Equalities like this ($xyz$? Sixth powers? I don't know the formula for that!) can look intimidating, but a cool head and some experience will make dealing with such unfamiliar things a bit more familiar.
Tempted to simplify the right hand side, we divide by three:
\[
\frac{x^6 + y^6 + z^6}{3} = 2xyz - 1
\]
The key of the exercise is to notice how the left hand side can be seen as an arithmetic average of 3 values, $x^6$, $y^6$ and $z^6$. Given how either the arithmetic average is always greater than the geometric average, or all the values are equal, we can consider the inequality:
\[
\sqrt[3]{x^6y^6z^6} \leq \frac{x^6 + y^6 + z^6}{3}
\]
And we simplify:
\[
x^2y^2z^2 \leq \frac{x^6 + y^6 + z^6}{3}
\]
We now define $xyz = t$, and proceed to exchange the fraction by the equivalence we first saw:
\[
t^2 \leq 2t - 1
\]
Therefore $(t-1)^2 \leq 0$, which is only possible for $t=1$ (since any other value will result in a positive square).
Now, since the product of the three variables is 1, $\sqrt[3]{x^6y^6z^6} = \sqrt[3]{1^6} = 1$, and going back to the initial equality, $2xyz - 1 = 2 - 1 = 1$, which is equal as well to the arithmetic average, we find that both the $AM$ and the $GM$ are equal, and therefore their elements are equal as well. Then:
\[
x^6 + x^6 + x^6 = 3x^6 = 3
\]
And so $x^6 = 1$. We find six solutions for $x$, all of them being either 1 or -1, but we have to restrict to combinations such that $xyz = 1$, which is left as a petty exercise for the reader.
We did this problem in class, and everyone was quite fascinated with how the problem simply unraveled with the use of such elementary methods. Admittedly, it's a very synthetic problem, but it testes your ability to see that which is not immediately obvious to the eye.
Problem 3. Any power $n^k$ can be expressed as the sum of $n$ consecutive odd integers.
This one comes from proving the $2^k$ case, and then being asked to do the same with $3^k$. It seemed too good to be true, but as it turns out, the proof is quite simple.
We assert the theorem:
\[
n^k = (2q + 1) + (2q + 3) + (2q + 5) + ... + (2q + (2n - 1))
\]
Let's reorder this:
\[
n^k = n2q + (1 + 3 + 5 + 7 + ... (2n - 1))
\]
It is a fact that the sum of the first $r$ odds is equal to $r^2$ (it's a one-line proof), so:
\[
n^k = n2q + n^2
\]
We find $q$:
\[
q = \frac{n^{k-1} - n}{2}
\]
And then verify the identity:
\[
n^k = n2\left(\frac{n^{k-1} - n}{2}\right) + n^2 = n(n^{k-1} - n) = n^n - n^2 + n^2 = n^k
\]
And we're done; the identity derived from the sum of $n$ consecutive odd integers is proved to be equal to $n^k$!
Equalities like this ($xyz$? Sixth powers? I don't know the formula for that!) can look intimidating, but a cool head and some experience will make dealing with such unfamiliar things a bit more familiar.
Tempted to simplify the right hand side, we divide by three:
\[
\frac{x^6 + y^6 + z^6}{3} = 2xyz - 1
\]
The key of the exercise is to notice how the left hand side can be seen as an arithmetic average of 3 values, $x^6$, $y^6$ and $z^6$. Given how either the arithmetic average is always greater than the geometric average, or all the values are equal, we can consider the inequality:
\[
\sqrt[3]{x^6y^6z^6} \leq \frac{x^6 + y^6 + z^6}{3}
\]
And we simplify:
\[
x^2y^2z^2 \leq \frac{x^6 + y^6 + z^6}{3}
\]
We now define $xyz = t$, and proceed to exchange the fraction by the equivalence we first saw:
\[
t^2 \leq 2t - 1
\]
Therefore $(t-1)^2 \leq 0$, which is only possible for $t=1$ (since any other value will result in a positive square).
Now, since the product of the three variables is 1, $\sqrt[3]{x^6y^6z^6} = \sqrt[3]{1^6} = 1$, and going back to the initial equality, $2xyz - 1 = 2 - 1 = 1$, which is equal as well to the arithmetic average, we find that both the $AM$ and the $GM$ are equal, and therefore their elements are equal as well. Then:
\[
x^6 + x^6 + x^6 = 3x^6 = 3
\]
And so $x^6 = 1$. We find six solutions for $x$, all of them being either 1 or -1, but we have to restrict to combinations such that $xyz = 1$, which is left as a petty exercise for the reader.
We did this problem in class, and everyone was quite fascinated with how the problem simply unraveled with the use of such elementary methods. Admittedly, it's a very synthetic problem, but it testes your ability to see that which is not immediately obvious to the eye.
Problem 3. Any power $n^k$ can be expressed as the sum of $n$ consecutive odd integers.
This one comes from proving the $2^k$ case, and then being asked to do the same with $3^k$. It seemed too good to be true, but as it turns out, the proof is quite simple.
We assert the theorem:
\[
n^k = (2q + 1) + (2q + 3) + (2q + 5) + ... + (2q + (2n - 1))
\]
Let's reorder this:
\[
n^k = n2q + (1 + 3 + 5 + 7 + ... (2n - 1))
\]
It is a fact that the sum of the first $r$ odds is equal to $r^2$ (it's a one-line proof), so:
\[
n^k = n2q + n^2
\]
We find $q$:
\[
q = \frac{n^{k-1} - n}{2}
\]
And then verify the identity:
\[
n^k = n2\left(\frac{n^{k-1} - n}{2}\right) + n^2 = n(n^{k-1} - n) = n^n - n^2 + n^2 = n^k
\]
And we're done; the identity derived from the sum of $n$ consecutive odd integers is proved to be equal to $n^k$!
Wednesday, February 4, 2015
Snow
Today has been a snowy day (not in the most rigorous sense of the word) all around the country. The camera struggled with such little amount of light, but it pulled this one off somehow, which looks cool enough.
Monday, February 2, 2015
Visit to the MNAC (National Art Museum of Catalonia)
This weekend i visited the National Art Museum of Catalonia for a few hours. Sadly, i couldn't take the camera with me, so all pictures were taken with my phone.
Subscribe to:
Posts (Atom)