Non-Trivial t-Intersection in the Function Lattice

The function lattice, or generalized Boolean algebra, is the set of ℓ-tuples with the ith coordinate an integer between 0 and a bound n_i. Two ℓ-tuples t-intersect if they have at least t common nonzero coordinates. We prove a Hilton–Milner type theorem for systems of t-intersecting ℓ-tuples.Received September 29, 2004     

Primitive Groups with no Regular Orbits on the Set of Subsets

We determine all primitive groups which do not have a regularorbit on the power set of the permutation domain. As a corollary,we also determine all families of orbit equivalent primitivepermutation groups. 1991 Mathematics Subject Classification20B15.     

Maximal triangle-free graphs with restrictions on the degrees

We investigate the problem that at least how many edges must a maximal triangle-free graph on n vertices have if the maximal valency is ≤D. Denote this minimum value by F(n, D). For large enough n, we determine the exact value of F(n, D) if D ≥ (n ? 2)/2 and we prove that lim F(n, cn)/n = K(c) exists for all 0 < c with the possible exception of a sequence c_k → 0. The determination of K(c) is a finite problem on all intervals [γ, ∞). For D = cn^?, 1/2 < ? < 1, we give upper and lower bounds for F(n, D) differing only in a constant factor. (Clearly, D < (n - 1)^1/2 is impossible in a maximal triangle-free graph.)     

Nearly Linear Time Algorithms for Permutation Groups: An Interplay Between Theory and Practice

We survey polynomial time algorithms (both deterministic and random) for computations with permutation groups. Particular emphasis is given to algorithms with running time of the form O(n log ^c |G|), where G is a permutation group of degree n. In the case of small-base groups, i.e., when log |G| is polylogarithmic as a function of n, such algorithms run in nearly linear, O(n log^c' n) time. Important classes of groups, including all permutation representations of simple groups except the alternating ones, as well as most primitive groups, belong to this category. For large n, the majority of practical computations is carried out on small-base groups.In the last section, we present some new nearly linear time algorithms, culminating in the computation of the upper central series in nilpotent groups.     

Local 2-Geodesic Transitivity of Graphs

An s-geodesic in a graph Γ is a path connecting two vertices at distance s. Being locally transitive on s-geodesics is not a monotone property: if an automorphism group G of a graph Γ is locally transitive on s-geodesics, it does not follow that G is locally transitive on shorter geodesics. In this paper, we characterise all graphs that are locally transitive on 2-geodesics, but not locally transitive on 1-geodesics.     

Bounds on the diameter of Cayley graphs of the symmetric group

In this paper we are concerned with the conjecture that, for any set of generators S of the symmetric group \(\operatorname {Sym}(n)\) , the word length in terms of S of every permutation is bounded above by a polynomial of n. We prove this conjecture for sets of generators containing a permutation fixing at least 37 % of the points.     

The Minimal Base Size of Primitive Solvable Permutation Groups

A base of a permutation group G is a sequence B of points fromthe permutation domain such that only the identity of G fixesB pointwise. Answering a question of Pyber, we prove that allprimitive solvable permutation groups have a base of size atmost four.     

Bounded Degree, Triangle Avoidance Graph Games

We consider variants of the triangle-avoidance game first defined by Harary and rediscovered by Hajnal a few years later. A graph game begins with two players and an empty graph on n vertices. The two players take turns choosing edges within K _n , building up a simple graph. The edges must be chosen according to a set of restrictions ${\mathcal{R}}$ . The winner is the last player to choose an edge that does not violate any of the restrictions in ${\mathcal{R}}$ . For fixed n and ${\mathcal{R}}$ , one of the players has a winning strategy. For various games where ${\mathcal{R}}$ includes bounded degree and triangle avoidance, we determine the winner for all values of n.     

The Number of Directions Determined by Points in the Three-Dimensional Euclidean Space

Abstract. Let X be a set of n points in the three-dimensional Euclidean space such that no three points in X are on the same line and there is no plane containing all points in X . An old conjecture states that pairs of points in X determine at least 2n-3 directions. We prove the weaker result that X determines at least 1.75n-2 directions.     

Quick gossiping without duplicate transmissions

There aren people, each knowing a gossip. They communicate by phone calls, and whenever two persons talk they tell all information they know at that time. Denote byf(n) the minimal number of necessary calls when everybody hears each gossip exactly once. We prove thatf(n) = 2.25n – 6 ifn = 4k, k 2 and 2.25n – 4.5 f(n) 2.25n – 3.5 ifn = 4k + 2,k 5. (Ifn is odd, orn = 4k + 2, 0 <k < 5 then there are no appropriate sequences of calls at all.)