Maximum size of a family of pairwise graph-different permutations (Q2411509)

Summary: Two permutations of the vertices of a graph \(G\) are called \(G\)-different if there exists an index \(i\) such that \(i\)-th entry of the two permutations form an edge in \(G\). We bound or determine the maximum size of a family of pairwise \(G\)-different permutations for various graphs \(G\). We show that for all balanced bipartite graphs \(G\) of order \(n\) with minimum degree \(n/2 - o(n)\), the maximum number of pairwise \(G\)-different permutations of the vertices of \(G\) is \(2^{(1-o(1))n}\). We also present examples of bipartite graphs \(G\) with maximum degree \(O(\log n)\) that have this property. We explore the problem of bounding the maximum size of a family of pairwise graph-different permutations when an unlimited number of disjoint vertices is added to a given graph. We determine this exact value for the graph of 2 disjoint edges, and present some asymptotic bounds relating to this value for graphs consisting of the union of \(n/2\) disjoint edges.