Some musical discoveries

I have been doing a summer project at ICFO for the past few days. The two hours of commute allow me to focus on music and nothing else, so I have been listening to some classical music podcasts by RTVE Radio Clásica, mostly Sala de Cámara and Sinfonía de la mañana.

Here is a list of pieces that I have enjoyed, with some updates planned for the near future.

• Sonata violoncelo e piano, Luís de Freitas Branco
• String quartet no. 14 in A# major, Dvořak
• Trio in D minor: Élegie, Arensky
• Introduction and Allegro for Harp, Flute, Clarinet and String Quartet, Ravel
• Todd und Verklärung, Richard Strauss
• Langsamer Satz, Webern
• String quartet no. 6 in F minor, Mendelssohn
• String quartet no. 2: Notturno, Borodin

Where am I and where am I going

'Tis a struggle often fought in my minds.

I have finally fully digested and accepted (or so I like to believe) that I will study at the University of Chicago for the next four years of my life. On a global scale, four years are merely a breeze, a blink of an eye, but I am in years, merely so, a pale leaf whirled about by this great winds. I am excited to jump into adulthood with such a challenge, both intellectual and personal, but there are always buts.

Great hopes and expectations, and doubts and fears are equally distributed in my dreams for the future. I desire to grow into the person that I dream of becoming, and leaving home is by necessity part of the whole package. I have felt many things that I didn't think I would, prompting me to read more into my inner and unconscious thoughts. Homesickness, or the very thought of predicted homesickness is, sadly, very real.

I am reading literature and math, trying to figure out what Love is in a relationship (capitalized to avoid forgetting), and gathering forces to lose all fears.

I end this short update, hopefully with more to come (as always, I strive to write more, but never quite strike), with a small poem by John Keats, always lyrical and evocative:

‘O thou whose face hath felt the Winter’s wind;
Whose eye has seen the Snow clouds hung in Mist
And the black-elm tops ’mong the freezing Stars
To thee the Spring will be a harvest-time—
O thou whose only book has been the light
Of supreme darkness which thou feddest on
Night after night, when Phoebus was away
To thee the Spring shall be a tripple morn—
O fret not after Knowledge—I have none
And yet my song comes native with the warmth
O fret not after Knowledge—I have none
And yet the Evening listens—He who saddens
At thought of Idleness cannot be idle,
And he’s awake who thinks himself asleep.’

"The Dream of a Ridiculous Man"

And yet it's so simple: in one day, in one hour - it could all be set up at once! The main thing is -- love others as yourself, that's the main thing, and it's everything, there's no need for anything else at all: it will immediately be discovered how to set things up. And yet this is merely an old truth, repeated and read a billion times, but still it has never taken root! "The consciousness of life is higher than life, the knowledge of the laws of happiness is higher than happiness" -- that is what must be fought! And I will. If only everyone wants it, everything can be set up at once.
And I found that little girl . . . And I'll go! I'll go!

-- The Dream of a Ridiculous Man, F.M. Dostoyevski

I have been working on some book typesetting, and a few things are almost ready to be shared. This is not one of them though; at least not the English translation.

Understanding convex polytopes (III)

This entry marks the end of my short series of posts regarding convex polytopes and graph-associahedra. I've had lots of fun and learned a lot during this month of research. Here follows a summary of the conclusions of our work.

Understanding the polytope made from $\text{Cycle}_n$ in a constructive manner proved to be harder than anticipated, and we summed up our work in this area with a conjecture relating the $\mathcal{B}$-trees of the cycle on $n+1$ vertices with the lattice paths on the $n \times n$ grid. Recall that the $\mathcal{B}$-trees of the cycle are just binary trees with an extra root at $n+1$, with a certain $\pmod{n+1}$ shift applied to the labels. We can define an equivalence relation based on this operation, and say that two trees $T_1$ and $T_2$ are congruent if they are generated from the same binary tree (with an extra root) $T$. Let $[T]$ denote the equivalence class of $n+1$ trees generated by a canonical binary tree $T$ and the shifting operation. We proceed to define the other side of the relation, lattice paths.

There is a direct construction of lattice paths from $(0,0)$ to $(n,n)$ on the $n \times n$ grid, in particular Dyck paths (those which do not cross the diagonal), from binary trees by expressing a binary tree as a balanced parenthesis sequence. We need to define a parallel of descent for lattice paths, for that is the center of our conjecture. Let $\text{peaks}(P)$ be the number of left-peaks of a lattice path; from the parenthesized construction, a left-peak in the Dyck path is equivalent to a descent in the binary tree. Next, we need to find an operation which serves as parallel for our label shifting on trees. There is a cool operation on Dyck paths (defined by Chen in [1]) which generates a set of $n+1$ lattice paths, and so we define again an equivalence relation based on this operation, with $[P]$ denoting the equivalence class of lattice paths generated from a Dyck path $P$. For distinct $P$ and $P'$, we can show that $[P] \cap [P'] = \varnothing$, and equivalently for our canonical binary trees.

As stated, there is a map $\Phi : \text{binary trees} \rightarrow \text{Dyck paths}$, and we conjecture that the descent generating function of the equivalence class $[T]$ is equal to the descent generating function of the equivalence class $[\Phi(T)]$:

$$\sum_{T' \in [T]} x^{\text{des}(T')} = \sum_{P' \in [\Phi(T)]} x^{\text{peaks}(P')}$$

We verified the conjecture for $n$ up to 13.

On the other hand, we found a combinatorial interpretation for the $\gamma$-polynomial of the cyclohedron. Following the approach of Posntnikov et al. in [2], we defined yet another delicate operation on lattice paths, allowing us to arrive to the desired $\gamma(x) = \sum_{r=0}^{\left \lfloor{\frac{n}{2}}\right \rfloor}\binom{n}{r,r,n-2r} x^r$ in a nice combinatorial way, in contrast to the previous work based on hyper-geometric series manipulations on the $h$-polynomial.

In conclusion, I am extremely happy of the work we've done, considering my very limited exposure to advanced mathematics (and even less to research level mathematics!). I enjoyed the research experience, and the constant unknown factor was such a motivator to keep me going; what's this? What if I do that? Are we doing the right thing? Is there another point of view? I am certainly convinced to pursue mathematics for as long as I can.

References

[1] Chen, Y. M. (2008), The Chung–Feller theorem revisited. Discrete Mathematics, 308(7), 1328-1329.
[2] Postnikov, A., Reiner, V., & Williams, L. (2008). Faces of generalized permutohedra. Doc. Math, 13(207-273), 51.

Understanding convex polytopes (II)

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.

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.

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).