✦ LIBER ✦

Derangements on the n-cube

✍ Scribed by William Y.C. Chen; Richard P. Stanley

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 599 KB
Volume: 115
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90479-d

No coin nor oath required. For personal study only.

✦ Synopsis

Chen, W.Y.C. and R.P. Stanley, Derangements on the n-cube, Discrete Mathematics 115 (1993) 65-15. Let Q. be the n-dimensional cube represented by a graph whose vertices are sequences of O's and l's of length n, where two vertices are adjacent if and only if they differ only at one position. A k-dimensional subcube or a k-face of Q. is a subgraph of Q. spanned by all the vertices u1 u2

with constant entries on n-k positions. For a k-face Gx of Q. and a symmetry w of Q., we say that w fixes Gt if w induces a symmetry of Gt; in other words, the image of any vertex of G,, is still a vertex in Gk. A symmetry w of Q. is said to be a k-dimensional derangement if w does not fix any k-dimensional subcube of Q.; otherwise, w is said to be a k-dimensional rearrangement.

In this paper, we find a necessary and sufficient condition for a symmetry of Q. to have a fixed kdimensional subcube. We find a way to compute the generating function for the number of k-dimensional rearrangements on Q.. This makes it possible to compute explicitly such generating functions for small k. Especially, for k =O, we have that there are 1.3

. (2n-1) symmetries of Q.

with at least one fixed vertex. A combinatorial proof of this formula is also given.

📜 SIMILAR VOLUMES

Stratified random walks on the n-cube

✍ F. R. K. Chung; R. L. Graham 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 226 KB 👁 1 views

In this paper we present a method for analyzing a general class of random ## Ž . walks on the n-cube and certain subgraphs of it . These walks all have the property that the transition probabilities depend only on the level of the point at which the walk is. For these walks, we derive sharp bound

Hamilto-connected derangement graphs on

Hamilto-connected derangement graphs on S n

✍ David J. Rasmussen; Carla D. Savage 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 476 KB

A note on the edges of the n-cube

✍ Sergiu Hart 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 671 KB

The following combinatorial problem, which arose in game theory, is solved here: To tind a selt of vertices of ;P given size (in t.k nxube) which has a maximal number sf interconnecting edges,

On a problem of Yuzvinsky on separating

On a problem of Yuzvinsky on separating the n-cube

✍ D.J. Kleitman 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 474 KB

The following problem of Yuzvinsky is solved here: how many vertices of the n-cube must be removed from it in order that no connected component of the rest contains an antipodal pair of vertices? Some further results and problems are described as well.

The Deranged

✍ Kate Myers 📂 Fiction 📅 2019 🏛 Kate Myers 🌐 English ⚖ 116 KB

Max has graduation on the brain, not a deadly plague. All was going according to plan, when an unknown virus hits his hometown and symptoms quickly change from “flu-like” to erratic and violent. With only minimal belongings, a gun, and his untested conscience, Max and his dad leave the cit

Poisson Convergence in the n-Cube

✍ Karl Weber 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 426 KB

We consider two types of random subgraphs of the n-cube Q, obtained by independent deletion the vertices (together with all edges incident with them) or the edges of Q,,, respectively, with a prescribed probability q = 1p . For these two probabilistic models we determine some values of the probabili