IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Independent set permutations and matching permutations

  • Oct. 2, 2020
  • 2:30 p.m.


In 1987 Alavi, Malde, Schwenk and Erdős showed that the independent set sequence of a graph is unconstrained in terms of its pattern of rises and falls, in the following sense: for any $m \in {\mathbb N}$ and any permutation $\pi$ of $\{1,2,\ldots, m\}$ there is a graph with largest independent set having size $m$, and with

$$ i _ {\pi(1)} \leq i _ {\pi(2)} \leq \cdots \leq i _ {\pi(m)} $$

where $i _ k$ is the number of independent sets of size $k$ in the graph. Their construction yielded a graph with around $m^{2m}$ vertices, and they raised the following question:

Determine the smallest order large enough to realize every permutation of order $m$ as the sorted indices of the vertex independent set sequence of some graph.

We answer this question exactly. Alavi et al. also observed that the matching sequence of a graph is, by contrast, quite constrained — at most $2^{m-1}$ permutations of $\{1,2,\ldots, m\}$ can be realized as the sorted indices of the matching sequence of some graph. They asked whether the upper bound of $2^{m-1}$ was optimal; we show that it is not. Many open problems remain in this area.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster