Combinatorics and Number Theory Seminar

We outline a complete and self-contained treatment of the asymptotics of (discrete and continuous) consensus and diffusion on directed graphs. Let G be a weakly connected directed graph with directed graph Laplacian L. In many or most applications involving digraphs, it is possible to identify a direction of flow of information. We fix that direction as the direction of the edges. With this convention, consensus (and its discrete-time analogue) and diffusion (and its discrete-time analogue) are dual to one another in the sense that ẋ = −Lx for consensus, and ṗ = −pL for diffusion. As a result, their asymptotic states can be described as duals.

We give a precise characterization of a basis of row vectors of the left null-space of L and of a basis of column vectors of the right null-space of L. This characterization is given in terms of the partition of G into strongly connected components and how these are connected to each other. In turn, this allows us to give a complete characterization of the asymptotic behavior of both diffusion and consensus in terms of these eigenvectors.

As an application of these ideas, we present a treatment of the pagerank algorithm that is dual to the usual one, and give a new result that shows that the teleporting feature usually included in the algorithm actually does not add information.

We will prove a beautiful result of Fagin from 1973 (and independently Glebskii Kogan, Liagonkii and Talanov) where it was shown that every sentence in first-order logic will be true with probability 0 or 1 in a model—aptly named the Zero-One Law for First-Order Logic. In particular, we will use random graphs with constant probability to show that every statement that can be expressed within first-order logic in the language of non-directed graphs will be realized with probability 0 or 1. An extension of this result, known as Fagin's Theorem, connects sentences expressible in second-order logic to exactly the class of problems in complexity theory known as NP. This provides us with a new way to approach the famous open problem of P vs. NP. If time permits, we will look at the evolution of random graphs where the probability of an edge being drawn is considered a function of the number of vertices. This leads to some surprising results of Erdos and Renyi regarding thresholds when certain properties of graphs occur. This talk will assume no advanced background in logic, random graphs or complexity theory.

Elimination of unknowns for systems of equations, starting with Gaussian elimination, is a classical problem with numerous applications. This problem can be stated as follows. Given a system of equations in m + n variables, determine whether there is a consequence of the system involving only the first m variables and find such a consequence if it exists.
In the talk, I will present my recent results yielding a new algorithm for elimination of unknowns for systems of differential equations and the first known algorithm for elimination of unknowns for systems of nonlinear recurrence relations (difference equations). I will describe applications of these results to modeling (in particular, to assessing parameter identifiability of differential models) and discrete mathematics (in particular, to enumerative combinatorics).