Premium
Independent set and matching permutations
Author(s) -
Ball Taylor,
Galvin David,
Hyry Catherine,
Weingartner Kyle
Publication year - 2022
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22724
Subject(s) - combinatorics , mathematics , permutation graph , permutation (music) , cyclic permutation , independent set , bit reversal permutation , upper and lower bounds , partial permutation , discrete mathematics , random permutation , matching (statistics) , derangement , permutation group , graph , set (abstract data type) , symmetric group , computer science , statistics , programming language , mathematical analysis , physics , acoustics
Let G be a graph G whose largest independent set has size m . A permutation π of { 1 , … , m } is an independent set permutation of G if a π ( 1 )( G ) ≤ a π ( 2 )( G ) ≤ ⋯ ≤ a π ( m )( G ) , where a k ( G ) is the number of independent sets of size k in G . In 1987 Alavi, Malde, Schwenk, and Erdős proved that every permutation of { 1 , … , m } is an independent set permutation of some graph with α ( G ) = m , that is, with the largest independent set having size m . They raised the question of determining, for each m , the smallest number f ( m ) such that every permutation of { 1 , … , m } is an independent set permutation of some graph with α ( G ) = m and with at most f ( m ) vertices, and they gave an upper bound on f ( m ) of roughly m 2 m . Here we settle the question, determining f ( m ) = m m , and make progress on a related question, that of determining the smallest order such that every permutation of { 1 , … , m } is the unique independent set permutation of some graph of at most that order. More generally we consider an extension of independent set permutations to weak orders, and extend Alavi et al.'s main result to show that every weak order on { 1 , … , m } can be realized by the independent set sequence of some graph with α ( G ) = m and with at most m m + 2vertices. Alavi et al. also considered matching permutations , defined analogously to independent set permutations. They observed that not every permutation of { 1 , … , m } is a matching permutation of some graph with the largest matching having size m , putting an upper bound of 2 m − 1on the number of matching permutations of { 1 , … , m } . Confirming their speculation that this upper bound is not tight, we improve it to O ( 2 m ∕ m ) .