Universal graphs and universal permutations

Let X be a family of graphs and X_n the set of n-vertex graphs in X. A graph U⁽ⁿ⁾ containing all graphs from X_nn as induced subgraphs is called n-universal for X. Moreover, we say that U⁽ⁿ⁾⁽ⁿ⁾ is a propern-universal graph for X if it belongs to X. In the present paper, we construct a proper n-universal graph for the class of split permutation graphs. Our solution includes two ingredients: a proper universal 321-avoiding permutation and a bijection between 321-avoiding permutations and symmetric split permutation graphs. The n-universal split permutation graph constructed in this paper has 4n³⁽ⁿ⁾ vertices, which means that this construction is order-optimal.