| Name: | Aaditya Raghavan |
|---|---|
| Email: | araghavan[at]gatech[dot]edu |
| Home Institution: | Georgia Institute of Technology |
| Project: | Counting Spanning Trees using Degrees of Vertices |
| Mentor: | Professor Bhargav Narayanan |
About My Project
For a given $n \in \mathbb{N}$, the number of spanning trees on $n$ labelled vertices is given by Cayley's famous formula, $n^{n-2}$, for which there are a plethora of proofs. Denoting $\tau(G)$ to be the number of spanning trees of $G$, another way of stating Cayley's result is $\tau(K_n) = n^{n-2}$. For more general graphs $G$, $\tau(G)$ can be expressed as a determinant, in particular, Kirchhoff's Matrix-Tree Theorem gives us that $\tau(G)$ is equal to any cofactor of the Laplacian of $G$. An interesting question in this line of thought is to determine whether we can estimate, via some upper bound, the quantity $\tau(G)$ for a given graph $G$, using the degrees of the vertices of $G$. Some results in this direction are stated and proved in [1] and [2], giving the upper bounds $\displaystyle \tau(G) \leq \frac{1}{|V(G)|^2}\prod_{v \in V(G)} (\text{deg}_G(v) + 1)$ and $\displaystyle \tau(G) \leq \frac{1}{|V(G)| - 1}\prod_{v \in V(G)}\text{deg}_G(v)$ respectively. Clearly, the former bound is tight for $K_n$ appealing to Cayley's formula. A seemingly unrelated inequality at first glance (which is in fact related closely to a weighted version of the former bound) is also a point we wish to investigate further and prove: $$\sum_{\sigma \in S_n}\text{cyc}(\sigma) \geq \sum_{\sigma \in S_n}\text{ord}(\sigma),$$ where, given a weight-assigning function $\displaystyle \alpha : {[n] \choose 2} \to \mathbb{R}^+ \cup \{0\}$, $\displaystyle \text{cyc}(\sigma) = \prod_{i=1}^n \alpha(\{i, \sigma(i)\})$ and $\displaystyle \text{ord}(\sigma) = \prod_{i=1}^{n-1}\alpha(\{\sigma(i), \sigma(i+1)\})$. When thinking about this inequality in the context of graphs, we often restrict our focus within the domain of $\alpha$ to be $E(G)$ and the weights assigned by $\alpha$ to non-edges to be $0$. Another question we can ask is, well, can we do better for certain classes of graphs, bipartite graphs, say? A curious conjecture in this direction is due to Ehrenborg - given a bipartite graph $G$ with bipartition $V(G) = A \sqcup B$, is it true that $$\tau(G) \leq \frac{1}{|A||B|}\prod_{v \in V(G)} \text{deg}_G(v)?$$
Research Log
Week 1: May 24 - May 28
I met with Professor Narayanan to discuss about background material and the two main questions we are looking to tackle - the aforementioned cycle weight-order weight inequality, and Ehrenborg's conjecture. A preliminary task was to establish that the cycle weight-order weight inequality in fact implies the weighted version of the bound $\displaystyle \tau(G) \leq \frac{1}{|V(G)|^2} \prod_{v \in V(G)}(\text{deg}_G(v) + 1)$, in particular given $\alpha : E(G) \to \mathbb{R}^+ \cup \{0\}$, we have $\displaystyle \tau_{\alpha}(G) \leq \frac{1}{|V(G)|^2}\prod_{v \in V(G)}(\text{deg}^{\alpha}_{G}(v) + 1)$ where $\displaystyle \tau_{\alpha}(G) = \sum_{T}\prod_{e \in E(T)}\alpha(e)$ is a sum taken over all spanning trees $T$ of $G$, and $\displaystyle \text{deg}^{\alpha}_G(v) = \sum_{w \in N_G(v)}\alpha(\{v,w\}) = \sum_{w \in V(G)}\alpha(\{v,w\})$, where the last equality follows if we assume $\alpha$ assigns a weight of $0$ to non-edges. This weighted version of the upper bound was also stated and proved in [1]. Prior to Professor Narayanan sending me the Mathematica code to inspect the cycle weight-order weight inequality, I wrote some code in Python using the SymPy library to start understanding the form of the LHS and RHS of the inequality for various values of $n$. Once he sent over his code in Mathematica, I began to inspect it and make sense of the output, and began to read the other papers he sent over regarding the Ehrenborg conjecture.
Week 2: May 31 - June 4
After meeting with Professor Narayanan, I convinced myself of the fact that the cycle weight-order weight inequality implies the weighted version of the bound $\displaystyle \tau_{\alpha}(G) \leq \frac{1}{|V(G)|^2}\prod_{v \in V(G)}(\text{deg}_G^{\alpha}(v) + 1)$. The implication involves using a clever proof of Cayley's formula due to André Joyal (see, for example, this). He also provided me with some notes regarding the inequality, and possible ways to approach the problem. A preliminary observation is that $\displaystyle \sum_{\sigma \in S_n}\text{cyc}(\sigma)$ is, indeed, closely related to the determinant of the adjacency matrix of a suitably chosen graph (treat $[n]$ as vertices with adjacencies between them such that $\{i, \sigma(i)\}$ has weight $\alpha(\{i, \sigma(i)\})$ for each $\sigma \in S_n$), without the sign term - the quantity is known as a permanent. In fact, the form that I discussed on Tuesday is a form found after simplification using AM-GM of a very similar inequality, namely where the order weight of a permutation $\sigma$ is defined to be $\alpha(\sigma(1), \sigma(1))\cdot \alpha(\sigma(n), \sigma(n))\cdot \prod_{i=1}^{n-1}(\alpha(\sigma(i), \sigma(i+1)) \cdot \alpha(\sigma(i+1), \sigma(i)))$. In this way, one can interpret the order weight using the notion of a Hamiltonian path, which becomes useful. In the next weeks, I will be looking more deeply into the methods suggested by Professor Narayanan towards making progress on the cycle weight-order weight inequality we are interested in.
Week 3: June 7 - June 11
This week, I switched focus to Ehrenborg's conjecture and explored (and currently investigating further) a combinatorial approach to trying to prove it. Professor Narayanan provided a lot of reading related to the conjecture and linear algebraic tools people have developed so far in order to tackle the problem - I will pursue a similar direction after some more time with thinking about the aforementioned combinatorial approach. Since the conjecture not only holds but holds with equality in the case of Ferrers graphs, this is one case that Professor Narayanan suggested to consider as I make progress. This combinatorial approach is essentially the natural one one thinks of when seeing the conjecture - rearranging, we have that if $G$ is a graph with $V(G) = A \sqcup B$, the conjecture states that $\displaystyle |A||B|\tau(G) \leq \prod_{v \in V(G)}\text{deg}_G(v)$, and this can be interpreted in a similar manner to André Joyal's proof of Cayley's formula. Finding an appropriate injection is the tricky part, and verifying that it holds as a one-to-one correspondence for Ferrers graphs would ensure that the approach could be plausible.
Week 4: June 14 - June 18
The aforementioned combinatorial approach did not quite work, but gives insight into proving an injection from $A$ to $B$, where $A$ represents the set of directed Hamiltonian paths of a graph $G$ on a vertex set $[n]$, and permutations $\pi : [n] \mapsto [n]$ such that $\pi(v) \in N(v) \cup \{v\}$. After meeting with Professor Narayanan later this week, we decided to probe this combinatorial approach further, to see if we can solve related cases (not quite the conjecture itself), and perhaps consider whether the conjecture is true in certain families of bipartite graphs that haven't been explored in the literature (graphs like even cycles and trees, for example, have been proved previously). In addition to this, there is an inductive approach that is motivated by the proof technique introduced in [1], which I will explore going into the next week as well.
Week 5: June 21 - June 25
I decided to probe a different approach in parallel, motivated by a paper which I finished reading this week, considering the conjecture in the case of partly regular graphs ([3]). I also began looking at graph decompositions, which could be quite promising seeing that if the conjecture holds for two bipartite graphs, then we may create a new graph by joining two vertices (one in each of the two graphs), and the conjecture will also hold for this newly created graph (a proof is given in [4]). Naturally, one can notice after some work that more particular types of graphs start to appear for which the conjecture holds as well (say removing bridges in a graph leaves subgraphs, each of which satisfy the conjecture), but again we would like to see whether we can wiggle the proofs provided in [3] towards some generalization.
Week 6: June 28 - July 2
Graph decompositions, at least in the way I was thinking about it, is not as straightforward as I thought it to be, and after a discussion with Professor Narayanan, we concluded that it may be slightly more generalizable but nonetheless will not yield too much. A problem that arose was to consider, say, a 6-cycle with a chord dividing it into a 4-cycle and a path of length 3. From [4] we know that adding an edge between graphs that satisfy the conjecture results in a new graph which also satisfies the conjecture, but in the case of this particular graph, any recursive construction would require the simultaneous addition of two edges - trying to prove that the addition of two edges in a single step also preserves the inequality in the conjecture would be an idea, but it would not expand the class of graphs that satisfy the conjecture by too much. Right now, I began focusing on graph products which preserve bipartite-ness (for example, the cartesian product of graphs) and seeing how such a product behaves given factors that satisfy the conjectural inequality.
Week 7: July 5 - July 9
After reading some papers on the cartesian product of graphs (in general, not applied to bipartite graphs), an inequality relating the Laplacian eigenvalues, vertex degrees, and biparition sizes of the multiplicand graphs fell out of the calculations I carried out. Awaiting Professor Narayanan's response, I realized that a possible reason to look at one-side regularity in bipartite graphs is that in the corresponding Laplacian, either the top-left or bottom-right blocks (or both) is some multiple of the identity matrix, and so the block matrix commutes with laterally adjacent blocks - then, the determinant of the Laplacian which we are obviously interested in can be written as the determinant of a difference of products of the block matrices. I spent some time trying to uncover some structure we can exploit, which will probably continue into the next week. Mainly, regarding the first item, verifying some cases with a computer will prove useful. In terms of possible combinatorial interpretations of $\displaystyle \prod_{v}\text{deg}(v)$, it remains to see if there are alternatives to the one already discussed in previous weeks which might yield to a clever interpretation of the conjecture as a whole. I remain a little skeptical about this, however.
Week 8: July 12 - July 16
I verified the inequality obtained from dealing with the graph cartesian product for all bipartite graphs with at most 8 vertices - in fact, it is tight for $K_{2,2}$ and rather loose as the number of vertices increases. Furthermore, I am in the process of experimenting with an inductive method, in particular removing an edge iteratively in each step, preserves some type of bound on $\tau(G)$ (ideally we would like it to be at most the RHS of the inequality in Ehrenborg's conjecture). Using some lemmas from linear algebra, I developed another inequality which shows quite a bit of promise. Following Professor Narayanan's suggestions, I found that if we start with $K_{n,n}$ and remove an edge, then clearly the resulting graph $G'$ is Ferrers and therefore Ehrenborg's inequality holds with equality in the case of $G'$ (and, of course, for $K_{n,n}$ as well) which implied that there must be equality in the inequality I developed - it turns out that yes, the new inequality also holds with equality, which I was able to show by exploiting matrix symmetry and some lemmas on the determinant. Professor Naraynan also suggested looking at any Ferrers graph in general (not necessarily $K_{n,n}$) and deducing whether a similar thing occurs when removing an edge results also in a Ferrers graph - this, along with what more I can deduce from this inductive idea will be the tasks moving forward up to the presentation next week.
Week 9: July 19 - July 23
This week, I mainly worked on my final presentation and paper, working also on some results that we can achieve on the computer for questions asked in [4], as well as our inequality regarding the Cartesian product of graphs. One could use the aforementioned inductive method to prove results such as $K_{n,n}$ without a random edge not only satisfies the conjectural inequality, but the inequality holds with equality for such graphs. Furthermore, Dr. Narayanan sent me a very recent paper, [5], which introduces a new proof of Cayley's formula for singly rooted trees on the vertex set $[n]$, which made a clever bijection between the set of singly rooted trees with vertex set $[n]$, and $[n]^{n-1}$, sequences of length $n-1$ with each member being an element of $[n]$. One idea to explore further now is whether such a bijection can be extended to doubly rooted trees on a given vertex set in order to prove the existence of some injection between spanning trees of a bipartite graph $G$, $V(G) = A \sqcup B$, with a pair of points $(a,b) \in A \times B$, and the set of functions from $V(G)$ to $V(G)$ such that each vertex is sent to one of its neighbors. It looks likely that we will continue to work together on this after the program's official ending as well.
References & Links
[1] Klee, Steven, Narayanan, Bhargav, and Sauermann, Lisa. "Sharp estimates for spanning trees." arXiv preprint arXiv:2102.01669 (2021). Link[2] Kostochka, Alexandr V. "The number of spanning trees in graphs with a given degree sequence." Random Structures & Algorithms 6.2-3 (1995): 269-274.
[3] Volkova, Albina. "On the number of spanning trees in bipartite graphs." arXiv preprint arXiv:2009.06688 (2020). Link
[4] Koo, Cheng Wai. "A Bound on the Number of Spanning Trees in Bipartite Graphs." (2016). Link
[5] Addario-Barry, Louigi, Donderwinkel, Serte, Maazoun, Mickaël, and Martin, James. "A new proof of Cayley's formula." arXiv preprint arxiv:2107.09726 (2021). Link