Emil Verkama: Patterns and connectivity in inversion graphs

Abstract: A few years ago, Svante Linusson and I showed that certain pattern-avoiding permutations have a weird property: if they are neither "decomposable" nor "almost decomposable", then they must have lots of inversions. In this talk, my goal is to shed light on this result by rephrasing it in terms of inversion graphs. Being neither "decomposable" nor "almost decomposable" translates simply to a weaker version of 2-connectivity for the graph.

This point of view motivates the study of the usual version of 2-connectivity in inversion graphs. We will see that 2-connected inversion graphs always satisfy a certain nontrivial lower bound on the number of edges, and find an infinite class of patterns whose avoidance improves this bound. Moreover, both results happen to extend to k-connected inversion graphs. Summary: a general k-connected graph on n vertices has at least kn/2 edges; for inversion graphs, this improves to (k+1)n/2 (- some constant); and if we avoid a certain pattern, it improves further to kn (- some other constant).

Lastly, enlightened by this new perspective, we will return to the original weaker version of 2-connectivity and generalize the result I mentioned.