Исследовательский семинар 13 марта
Приглашаем на семинар, который состоится 13 марта (понедельник!) в 16.50.
Адрес: Кантемировская ул., дом 3,Высшая Школа Экономики, ауд. 356
Тема доклада: Generalization of binomial coefficients to numbers on the nodes of graphs
Докладчик: Anna Khmelnitskaya (ПМ-ПУ СпбГУ; University of Twente)
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.
Цель семинара – обсуждение work in progress,
своих или чужих идей, показавшихся интересными.
Приглашаются все желающие!