A non-technical journey through the basic structure and results on higher-rank graphs.
Tag - Graph theory
In the last few years, expanders have been used in fast graph algorithms in different models, including static, dynamic, and distributed algorithms. I will survey these applications of expanders, explain the expander-related tools behind this development, then give a tutorial on how to construct some of these tools, such as expander decomposition.
In a vertex expanding graph, every small subset of vertices neighbors many different vertices. Random graphs are near-optimal vertex expanders; however, it has proven difficult to create families of deterministic near-optimal vertex expanders, as the connection between vertex and spectral expansion is limited. We discuss successful attempts to create unique neighbour expanders (a weak version of vertex expansion), as well as limitations in using common combinatorial methods to create stronger expanders.
The boundary algebra of a dimer model derived from a Postnikov diagram may be used to obtain an additive categorification of the cluster algebra of the associated positroid variety. The boundary algebra has an explicit description in the case of Grassmannians but not for more general positroids. It is known that every Postnikov diagram is move equivalent to one which comes from a Le-diagram and has an isomorphic boundary algebra. We use the perfect matching structure of a dimer model derived from a Le-diagram to provide an algorithm for computing the Gabriel quiver and relations of its boundary algebra.
Given a group G and two vectors v and w in a representation V, one can ask: do v and w lie in the same orbit? This is what we call the orbit problem. For the action of GLn on m-tuples of n × n matrices, the orbit problem translates to the module isomorphism problem for which there is a known polynomial time algorithm. In joint work with Visu Makam, we also gave a polynomial time algorithm for deciding whether the orbit closures of v and w intersect. We also have similar results for the left-right action of SLn × SLn on the space of m-tuples of matrices. These results are related to interesting problems in algebraic complexity theory, such as non-commutative rational identity testing. The graph isomorphism problem can also formulated as an orbit problem. No polynomial time algorithm for the graph isomorphism problem is known. I will discuss an algorithm for the graph isomorphism problem that is more powerful than the higher-dimensional Weisfeiler-Leman algorithm when it comes to distinguishing pairs of non-isomorphic graphs in polynomial time. (This algorithm could potentially be polynomial time, but we will not make such a bold claim.)
Given a string Coxeter system (W,S), we construct highly regular quotients of the 1-skeleton of its universal polytope P, which form an infinite family of expander graphs when (W,S) is indefinite and P has finite vertex links. The regularity of the graphs in this family depends on the Coxeter diagram of (W,S). The expansion stems from superapproximation applied to (W,S). This construction is also extended to cover Wythoffian polytopes. As a direct application, we obtain several notable families of expander graphs with high levels of regularity, answering in particular a question posed by Chapman, Linial and Peled positively.
This talk is based on joint work with Marston Conder, Alexander Lubotzky and Francois Thilmany.
This video was produced by the Sydney Mathematical Research Institute, as part of their SMRI seminar series.
Computing many-body ground state energies and resolving electronic structure calculations are fundamental problems for fields such as quantum chemistry or condensed matter. Several quantum computing algorithms that address these problems exist, although it is often challenging to establish rigorous bounds on their performances. I shall first consider the general task of approximating the ground state energy of quantum Hamiltonians on bounded-degree graphs. I will discuss our approach to go beyond product state approximations for a quantum analog of the Max Cut problem, where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case - and more recent work by others has improved on this strategy further. We also show that for any instance defined by a 3 or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation). Then, I will describe our more recent work to generalize this approach to other bounded-degree local Hamiltonians, where we describe a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. Finally, I will discuss results demonstrating the performance of these algorithms via numerical experiments on a 2-dimensional Hubbard model, starting from a checkerboard product state, as well as on some chemistry Hamiltonians, using the Hartree-Fock state as reference. In both cases, we show that the approximate energies produced are close to the exact ones. These algorithms provide a way to systematically improve the estimation of ground state energies and can be used stand-alone or in conjunction with existing quantum algorithms for ground states.
Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any non-trivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold.
I will discuss the dictionary between the algebraic structure of a right-angled Artin group and the combinatorics of the defining graph. I will then use the cohomology of a right-angled Artin group to provide a characterization of Hamiltonicity of the underlying graph. Along the way, I will describe some linear algebraic facts which appear to have been previously unknown.
I will review two combinatorial constructions of integrable systems: Goncharov-Kenyon construction based on counting perfect matchings in bipartite graphs, and Gekhtman-Shapiro-Tabachnikov-Vainshtein construction based on counting paths in networks. After that I will outline my proof of equivalence of those constructions.
You must be logged in to post a comment.