Independent set and matching permutations

DOI10.1002/JGT.22724MaRDI QIDQ6056793zbMATH OpenOpenAlexFDO

Authors Taylor Ball, David Galvin

Publication date 4 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.06579

zbMATH Keywords

independent setmatchingpermutationstable setunimodality

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Let $G$ be a graph $G$ whose largest independent set has size $m$. A permutation $pi$ of $1,ldots,m$ is an {em independent set permutation} of $G$ if ${\displaystyle }$ a_{pi(1)}(G) leq a_{pi(2)}(G) leq cdots leq a_{pi(m)}(G) ${\displaystyle }$ where $a_k(G)$ is the number of independent sets of size $k$ in $G$. In 1987 Alavi, Malde, Schwenk and ErdH{o}s proved that every permutation of $1,ldots,m$ is an independent set permutation of some graph with $alpha(G)=m$, i.e. with 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,ldots,m$ is an independent set permutation of some graph with $alpha(G)=m$ and with at most $f(m)$ vertices, and they gave an upper bound on $f(m)$ of roughly $m^{2m}$. 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,ldots,m$ is the {em 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,ldots,m$ can be realized by the independent set sequence of some graph with $alpha(G)=m$ and with at most $m^{m+2}$ vertices. Alavi et al. also considered {em matching permutations}, defined analogously to independent set permutations. They observed that not every permutation of $1,ldots,m$ is a matching permutation of some graph with largest matching having size $m$, putting an upper bound of $2^{m-1}$ on the number of matching permutations of $1,ldots,m$. Confirming their speculation that this upper bound is not tight, we improve it to $O(2^m/sqrtm)$.

Recommendations

• Independent sets versus perfect matchings
• From matchings to independent sets
• Independent sets, matchings, and occupancy fractions
• Pattern avoiding permutations and independent sets in graphs
• Matchings up to permutations in sequences of independent trials
• scientific article; zbMATH DE number 4204350
• scientific article; zbMATH DE number 1445297
• Min-wise independent permutations
• On independent permutation separability criteria
• Alternating subsets and permutations

Cites work

• A bipartite graph with non-unimodal independent set sequence
• An asymptotic equivalent for the number of total preorders on a finite set
• Bounds on the number of complete subgraphs
• Face vectors of flag complexes
• scientific article; zbMATH DE number 5139526 (Why is no real title available?)
• scientific article; zbMATH DE number 4112649 (Why is no real title available?)
• Independence sequences of well-covered graphs: Non-unimodality and the roller-coaster conjecture
• Maximal-clique partitions and the roller coaster conjecture
• On the numbers of independent k-sets in a claw free graph
• On unimodal sequences of graphical invariants
• Pascal's Matrices
• Rook placements in Young diagrams and permutation enumeration
• Roots of independence polynomials of well covered graphs
• Shadows of colored complexes.
• The independent set sequence of some families of trees
• Theory of monomer-dimer systems

Cited in

(8)

• On the independent set sequence of a tree
• From matchings to independent sets
• Maximum size of a family of pairwise graph-different permutations
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• Independent sets versus perfect matchings
• The independence polynomial of trees is not always log-concave starting from order 26
• Log-concavity of the independence polynomials of \(\mathbf{W}_p\) graphs
• A symmetric function approach to log-concavity of independence polynomials

This page was built for publication: Independent set and matching permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6056793)