Georgia Institute of Technology College of Sciences

The talk presents an extension for high dimensions of an idea from a recent result concerning near optimal adaptive finite element methods (AFEM). The usual adaptive strategy for finding conforming partitions in AFEM is ”mark → subdivide → complete”. In this strategy any element can be marked for subdivision but since the resulting partition often contains hanging nodes, additional elements have to be subdivided in the completion step to get a conforming partition. This process is very well understood for triangulations received via newest vertex bisection procedure. In particular, it is proven that the number of elements in the final partition is limited by constant times the number of marked cells. This motivated us [B., Fierro, Veeser, in preparation] to design a marking procedure that is limited only to cells of the partition whose subdivision will result in a conforming partition and therefore no completion step is necessary. We also proved that this procedure is near best in terms of both error of approximation and complexity. This result is formulated in terms of tree approximations and opens the possibility to design similar algorithms in high dimensions using sparse occupancy trees introduced in [B., Dahmen, Lamby, 2011]. The talk describes the framework of approximating high dimensional data using conforming sparse occupancy trees.

I will talk about a conjecture that in Gibbs states of one-dimensional spin chains with short-ranged gapped Hamiltonians the quantum conditional mutual information (QCMI) between the parts of the chain decays exponentially with the length of separation between said parts. The smallness of QCMI enables efficient representation of these states as tensor networks, which allows their efficient construction and fast computation of global quantities, such as entropy. I will present the known partial results on the way of proving of the conjecture and discuss the probable approaches to the proof and the obstacles that are encountered.

To any finite real sequence, we can associate a permutation $\pi$, via: $\pi(k)$ is the index of the $k$th smallest element of the sequence. This association was introduced in a 1987 paper of Alavi, Malde, Schwenk and Erd\H{o}s, where they used it to study the possible patterns of rises and falls that can occur in the matching sequence of a graph (the sequence whose $k$th term is the number of matchings of size $k$), and in the independent set sequence. The main result of their paper was that {\em every} permutation can arise as the ``independent set permutation'' of some graph. They left open the following extremal question: for each $n$, what is the smallest order $m$ such that every permutation of $[n]$ can be realized as the independent set permutation of some graph of order at most $m$? We answer this question. We also improve Alavi et al.'s upper bound on the number of permutations that can be realized as the matching permutation of some graph. There are still many open questions in this area. This is joint work with T. Ball, K. Hyry and K. Weingartner, all at Notre Dame.