Stellar permutations of the two-element subsets of a finite set

Let X be a finite set and denote by X⁽²⁾ the set of 2-element subsets of X. A permutation ϕ of X⁽²⁾ is called stellar if, for each x in X, the image under ϕ of the star St(x) = {{x, y}: x ≠ y ∈ X} is a 2-regular graph spanning X − {x}. Several constructions of stellar permutations are given; in particular, there is a natural direct construction using self-orthogonal Latin squares, and a simple recursive construction using linear spaces having all line sizes at least four. Apart from some intrinsic interest, stellar permutations arise in the construction of certain designs. For example, applying such a map ϕ to each of the stars St(x) yields a double covering of the complete graph on X by near 2-factors. We also study stellar groups, that is groups {ϕ₁, …, ϕ_s} of permutations of X⁽²⁾ such that each ϕ_i is stellar (or the identity map). It is elementary to prove that s ≤ for any stellar group; when equality holds, one can construct an associated elation semibiplane. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 381–387, 1998     

Turning points in random permutations of two kinds of distinct elements

The mean and variance of the number of turning points in random permutations of two kinds of distinct elements are evaluated. These results are applied to a Wald–Wolfowitz run test.     

Independent set and matching permutations

Let $G$ be a graph $G$ whose largest independent set has size $m$. A permutation $\pi$ of $\left\{1,\text{…},m\right\}$ is an independent set permutation of $G$ if $$a_{\pi \left(1\right)}\left(G\right)\le a_{\pi \left(2\right)}\left(G\right)\le \mathrm{?}\le a_{\pi \left(m\right)}\left(G\right),$$ where $a_k\left(G\right)$ is the number of independent sets of size $k$ in $G$. In 1987 Alavi, Malde, Schwenk, and Erd?s proved that every permutation of $\left\{1,\text{…},m\right\}$ is an independent set permutation of some graph with $\alpha \left(G\right)=m$, that is, with the largest independent set having size $m$. They raised the question of determining, for each $m$, the smallest number $f\left(m\right)$ such that every permutation of $\left\{1,\text{…},m\right\}$ is an independent set permutation of some graph with $\alpha \left(G\right)=m$ and with at most $f\left(m\right)$ vertices, and they gave an upper bound on $f\left(m\right)$ of roughly $m^{2m}$. Here we settle the question, determining $f\left(m\right)=m^m$, and make progress on a related question, that of determining the smallest order such that every permutation of $\left\{1,\text{…},m\right\}$ 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 $\left\{1,\text{…},m\right\}$ can be realized by the independent set sequence of some graph with $\alpha \left(G\right)=m$ and with at most $m^{m+2}$ vertices. Alavi et al. also considered matching permutations, defined analogously to independent set permutations. They observed that not every permutation of $\left\{1,\text{…},m\right\}$ is a matching permutation of some graph with the largest matching having size $m$, putting an upper bound of $2^{m?1}$ on the number of matching permutations of $\left\{1,\text{…},m\right\}$. Confirming their speculation that this upper bound is not tight, we improve it to $O\left(2^m∕\sqrt{m}\right)$.     

On the number of k-subsets of a set of n points in the plane

For a configuration S of n points in $\text{E}$², H. Edelsbrunner (personal communication) has asked for bounds on the maximum number of subsets of size k cut off by a line. By generalizing to a combinatorial problem, we show that for 2k < n the number of such sets of size at most k is at most 2nk ? 2k² ? k. By duality, the same bound applies to the number of cells at distance at most k from a base cell in the cell complex determined by an arrangement of n lines in $\text{P}$².     

On fixed points of permutations

The number of fixed points of a random permutation of {1,2,…,n} has a limiting Poisson distribution. We seek a generalization, looking at other actions of the symmetric group. Restricting attention to primitive actions, a complete classification of the limiting distributions is given. For most examples, they are trivial – almost every permutation has no fixed points. For the usual action of the symmetric group on k-sets of {1,2,…,n}, the limit is a polynomial in independent Poisson variables. This exhausts all cases. We obtain asymptotic estimates in some examples, and give a survey of related results. This paper is dedicated to the life and work of our colleague Manfred Schocker. We thank Peter Cameron for his help. Diaconis was supported by NSF grant DMS-0505673. Fulman received funding from NSA grant H98230-05-1-0031 and NSF grant DMS-0503901. Guralnick was supported by NSF grant DMS-0653873. This research was facilitated by a Chaire d’Excellence grant to the University of Nice Sophia-Antipolis.     

On the set of points with a dense orbit

Under certain conditions on the topological space we prove that for every continuous map the set of all points with a dense orbit has empty interior in . This result implies a negative answer to two problems proposed by M. Barge and J. Kennedy.

     

A finite partially ordered set and its corresponding set of permutations

The paper presents a method for describing a finite partially ordered set by means of permutations. Such an approach is convenient, in particular, in studying variant orderings of the original set.Translated from Matematicheskie Zametki, Vol. 4, No. 5, pp. 511–518, November, 1968.In conclusion, I should like to thank the reviewer whose notes I used in preparing the final version of this paper. In particular, I owe to him the recursion method of computing m(A).     

Forbidden arithmetic progressions in permutations of subsets of the integers

Permutations of the positive integers avoiding arithmetic progressions of length 5 were constructed in Davis et al. (1977), implying the existence of permutations of the integers avoiding arithmetic progressions of length 7. We construct a permutation of the integers avoiding arithmetic progressions of length 6. We also prove a lower bound of $\frac{1}{2}$ on the lower density of subsets of positive integers that can be permuted to avoid arithmetic progressions of length 4, sharpening the lower bound of $\frac{1}{3}$ from LeSaulnier and Vijay (2011).     

Generating all subsets of a finite set with disjoint unions

If X is an n-element set, we call a family G⊂PX a k-generator for X if every x⊂X can be expressed as a union of at most k disjoint sets in G. Frein, Lévêque and Seb? conjectured that for n>2k, the smallest k-generators for X are obtained by taking a partition of X into classes of sizes as equal as possible, and taking the union of the power-sets of the classes. We prove this conjecture for all sufficiently large n when k=2, and for n a sufficiently large multiple of k when k?3.     

Extremal problems among subsets of a set

This paper is a survey of open problems and results involving extremal size of collections of subsets of a finite set subject to various restrictions, typically on intersections of members.     

Antichains in the set of subsets of a multiset

A set F of distinct subsets x of a finite multiset M (that is, a set with several different kinds of elements) is a c-antichain if for no c + 1 elements x₀, x₁, …, x_c of F does x₀ ? x₁ ? ··· ? x_c hold. The weight of F, wF, is the total number of elements of M in the various elements x of F. For given integers f and c, we find min wF, where the minimum is taken over all f-element c-antichains F. Daykin [9, 10] has solved this problem for ordinary sets and Clements [3] has solved it for multisets, but only for c = 1.