Research Seminar on March 13, 2017
Topic: Generalization of binomial coefficients to numbers on the nodes of graphs
Speaker: Anna Khmelnitskaya (ПМ-ПУ СпбГУ; University of Twente)
The workshop will take place at 3A Kantemirovskaya st., room 356 (3rd floor) at 16:50.
The triangular array of binomial coefficients, or Pascal's triangle, is formed by starting with an apex of 1. Every its row can be seen as a linear graph, to each node of which the corresponding binomial coefficient is assigned. We show that the binomial coefficient of a node is equal to the number of ways the linear graph can be constructed starting with this node and adding subsequently neighboring nodes one by one. Using this interpretation we generalize the sequences of binomial coefficients on rows of Pascal's triangle to so-called connectivity degrees assigned to the nodes of an arbitrary (connected) graph. We show that the connectivity degrees of nodes have properties very similar to that of binomial coefficients. We also show that for a given connected cycle-free graph the connectivity degrees of nodes, when normalized to sum up to one, are equal to the steady state probabilities of some Markov chain on the nodes. Because the connectivity degree of a node in a connected graph is defined as the number of ways the graph can be constructed by a sequence of increasing connected subgraphs starting from this node, the connectivity degrees of the nodes can be seen as a measure of centrality in a graph. On the subclass of connected cycle-free graphs we provide axiomatic characterization of this connectivity centrality measure.
yours and others ideas, which can be interesting.