The Preisach graph and longest increasing subsequences

DOI10.4171/AIHPD/151MaRDI QIDQ6338239arXivFDO

Authors Patrik Lino Ferrari, Muhittin Mungan, M. Mert Terzi

Publication date 7 April 2020

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Directed graphs (digraphs), tournaments (05C20) Planar graphs; geometric and topological aspects of graph theory (05C10) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Abstract: The Preisach graph is a directed graph associated with a permutation $hoin{calS}_N$. We give an explicit bijection between its vertices and increasing subsequences of $ho$ with the property that the length of a subsequence equals to the degree of nesting of the corresponding vertex inside a hierarchy of cycles and sub-cycles of the graph. As a consequence, the nesting degree of the Preisach graph equals the length of the longest increasing subsequence.

This page was built for publication: The Preisach graph and longest increasing subsequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6338239)