Universal graphs and universal permutations

Let X be a family of graphs and Xn the set of n-vertex graphs in X. A graph U(n) containing all graphs from Xn as induced subgraphs is called n-universal for X. Moreover, we say that U(n) 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 4n3 vertices, which means that this construction is order-optimal.