Permutations as Hypergraphs

Martin Klazar

KAM and ITI Malostranské náměstí 25 118 00 Praha Czech Republic  

klazar@kam.mff.cuni.cz

Abstract.      Full Text PDF

By a hypergraph we shall understand a finite list  of nonempty finite subsets  of the set . It will be important that  and its subsets are linearly ordered by the standard ordering . We say that  is contained in another hypergraph  if there is an increasing (with respect to ) injection  and an injection  such that  holds for every . If  is not contained in  we say that  is -free or that it avoids . For a fixed forbidden hypergraph , two kinds of questions can be asked on -free hypergraphs: enumerative (how many such hypergraphs are there) and extremal (e.g., what is the maximum possible number of their edges). Prominent role among forbidden hypergraphs  is played by permutation graphs . For a permutation  of ,  is defined by . In the lecture I will discuss enumerative and extremal problems and results on -free hypergraphs and will mention relations to other kinds of pattern avoidance.