Universal octonary diagonal forms over some real quadratic fields

In this paper, we will prove there are infinitely many integers n such that n ²— 1 is square-free and admits universal octonary diagonal quadratic forms. Received: November 2, 1998.     

Erdös Conjecture on Sums of Distinct Numbers

A conjecture of Erdös that a set of n distinct numbers having the most linear combinations with coefficients 0,1 all equal are n integers of smallest magnitude is here proven. The result follows from a theorem of Stanley that implies that the integers from n have the most such linear combinations having k distinct values for every k. The same result is shown to hold for complex numbers and vectors in Hilbert space. It is shown that the number of linear combinations taking on k distinct values is maximized by the same configuration, for every k. Generalization to the case in which irregular distinctness restrictions are imposed is also given.     

Sparse universal graphs for bounded‐degree graphs

Let ℋ︁ be a family of graphs. A graph T is ℋ︁‐universal if it contains a copy of each H ∈ℋ︁ as a subgraph. Let ℋ︁(k,n) denote the family of graphs on n vertices with maximum degree at most k. For all positive integers k and n, we construct an ℋ︁(k,n)‐universal graph T with edges and exactly n vertices. The number of edges is almost as small as possible, as Ω(n^2‐2/k) is a lower bound for the number of edges in any such graph. The construction of T is explicit, whereas the proof of universality is probabilistic and is based on a novel graph decomposition result and on the properties of random walks on expanders. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Representations of graphs modulo n

A graph is representable modulo n if its vertices can be labeled with distinct integers between 0 and n, the difference of the labels of two vertices being relatively prime to n if and only if the vertices are adjacent. Erd?s and Evans recently proved that every graph is representable modulo some positive integer. We derive a combinatorial formulation of representability modulo n and use it to characterize those graphs representable modulo certain types of integers, in particular integers with only two prime divisors. Other facets of representability are also explored. We obtain information about the values of n modulo which paths and cycles are representable.     

Engel words and the Restricted Burnside Problem

The following theorem is proved. For any positive integers n and k there exists a number s = s(n, k) depending only on n and k such that the class of all groups G satisfying the identity ^n 1{\left(\left[x_1, {}_ky_1\right] \cdots \left[x_s, {}_ky_s\right]\right)^n \equiv 1} and having the verbal subgroup corresponding to the kth Engel word locally finite is a variety.     

Latin squares with pairwise orthogonal conjugates

Let L¹ denote the set of integers n such that there exists an idempotent Latin square of order n with all of its conjugates distinct and pairwise orthogonal. It is known that L¹ contains all sufficiently large integers. That is, there is a smallest integer n_o such that L¹ contains all integers greater than n_o. However, no upper bound for n_o has been given and the term “sufficiently large” is unspecified. The main purpose of this paper is to establish a concrete upper bound for n_o. In particular it is shown that L¹ contain all integers n>5594, with the possible exception of n=6810.     

Degree sequences of <Emphasis Type="Italic">k</Emphasis>-multi-hypertournaments

Let n and k（n ≥ k 〉 1） be two non-negative integers.A k-multi-hypertournament on n vertices is a pair（V,A）,where V is a set of vertices with ｜V｜=n,and A is a set of k-tuples of vertices,called arcs,such that for any k-subset S of V,A contains at least one（at most k!） of the k! k-tuples whose entries belong to S.The necessary and suffcient conditions for a non-decreasing sequence of non-negative integers to be the out-degree sequence（in-degree sequence） of some k-multi-hypertournament are given.     

Large Deviations for Quicksort

LetQ_nbe the random number of comparisons made by quicksort in sortingndistinct keys when we assume that alln! possible orderings are equally likely. Known results concerning moments forQ_ndo not show how rare it is forQ_nto make large deviations from its mean. Here we give a good approximation to the probability of such a large deviation and find that this probability is quite small. As well as the basic quicksort, we consider the variant in which the partitioning key is chosen as the median of (2t+1) keys.     

Signed degree sets in signed graphs

The set D of distinct signed degrees of the vertices in a signed graph G is called its signed degree set. In this paper, we prove that every non-empty set of positive (negative) integers is the signed degree set of some connected signed graph and determine the smallest possible order for such a signed graph. We also prove that every non-empty set of integers is the signed degree set of some connected signed graph.     

Star chromatic number

A generalization of the chromatic number of a graph is introduced such that the colors are integers modulo n, and the colors on adjacent vertices are required to be as far apart as possible.     

On two classes of permutations with number-theoretic conditions on the lengths of the cycles

Let Λ be an arbitrary set of positive integers andS _n (Λ) the set of all permutations of degreen for which the lengths of all cycles belong to the set Λ. In the paper the asymptotics of the ratio |S _n (Λ)|/n! asn→∞ is studied in the following cases: 1) Λ is the union of finitely many arithmetic progressions, 2) Λ consists of all positive integers that are not divisible by any number from a given finite set of pairwise coprime positive integers. Here |S _n (Λ)| stands for the number of elements in the finite setS _n (Λ). Translated fromMatematicheskie Zametki, Vol. 62, No. 6, pp. 881–891, December, 1997. Translated by A. I. Shtern     

Complementary Regions of Knot and Link Diagrams

An increasing sequence of integers is said to be universal for knots and links if every knot and link has a reduced projection on the sphere such that the number of edges of each complementary face of the projection comes from the given sequence. In this paper, it is proved that the following infinite sequences are each universal for knots and links: (3, 5, 7, . . .), (2, n, n + 1, n + 2, . . .) for each n ≥ 3, (3, n, n + 1, n + 2, . . .) for each n ≥ 4. Moreover, the finite sequences (2, 4, 5) and (3, 4, n) for each n ≥ 5 are universal for all knots and links. It is also shown that every knot has a projection with exactly two odd-sided faces, which can be taken to be triangles, and every link of n components has a projection with at most n odd-sided faces if n is even and n + 1 odd-sided faces if n is odd.     

Degree frequencies in digraphs and tournaments

The number of vertices in a digraph G having a particular outdegree (indegree) is called the frequency of the outdegree (indegree). A set F of distinct positive integers {f₁, f₂, …, f_n} is the frequency set of the digraph G if every outdegree and indegree occurs with frequency f_j∈F and for each f_j∈F there is a least one outdegree and at least one indegree with frequency f_j. We prove that each nonempty set F of positive integers is the frequency set of some tournament, and we determine the smallest possible order for such a tournament. Similar results for asymmetric digraphs are also given. The results and techniques for frequency sets are used to derive corresponding results for vertex frequency partitions.     

Spanning triangulations in graphs

We prove that every graph of sufficiently large order n and minimum degree at least 2n/3 contains a triangulation as a spanning subgraph. This is best possible: for all integers n, there are graphs of order n and minimum degree ?2n/3? ? 1 without a spanning triangulation. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Values of the Euler Function in Various Sequences

Let ϕ(n) and λ(n) denote the Euler and Carmichael functions, respectively. In this paper, we investigate the equation ϕ(n)^r = λ(n)^s, where r ≥ s ≥ 1 are fixed positive integers. We also study those positive integers n, not equal to a prime or twice a prime, such that ϕ(n) = p − 1 holds with some prime p, as well as those positive integers n such that the equation ϕ(n) = f(m) holds with some integer m, where f is a fixed polynomial with integer coefficients and degree degf > 1.     

Irreducible 2‐fold cycle systems

In this paper, it is shown that for any pair of integers (m,n) with 4 ≤ m ≤ n, if there exists an m‐cycle system of order n, then there exists an irreducible 2‐fold m‐cycle system of order n, except when (m,n) = (5,5). A similar result has already been established for the case of 3‐cycles. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 324–332, 2006     

Generalized Büchi’s problem for algebraic functions and meromorphic functions

Büchi’s nth power problem asks is there a positive integer M such that any sequence ${(x_1^n,\ldots ,x_M^n)}$ of nth powers of integers with nth difference equal to n! is necessarily a sequence of nth powers of successive integers. In this paper, we study an analogue of this problem for meromorphic functions and algebraic functions.     

Multilevel and multidimensional Hadamard matrices

Multilevel Hadamard matrices (MHMs), whose entries are integers as opposed to the traditional restriction to {±1}, were introduced by Trinh, Fan, and Gabidulin in 2006 as a way to construct multilevel zero-correlation zone sequences, which have been studied for use in approximately synchronized code division multiple access systems. We answer the open question concerning the maximum number of distinct elements permissible in an order n MHM by proving the existence of an order n MHM with n elements of distinct absolute value for all n. We also define multidimensional MHMs and prove an analogous existence result.      

Hamiltonian paths and cycles in hypertournaments

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V| = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A$ contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertournament is merely an (ordinary) tournament. A path is a sequence v₁a₁v₂v₃···v_t−1v_t of distinct vertices v₁, v₂,⋖, v_t and distinct arcs a₁, ⋖, a_t−1 such that v_i precedes v_t−1 in a, 1 ≤ i ≤ t − 1. A cycle can be defined analogously. A path or cycle containing all vertices of T (as v_i's) is Hamiltonian. T is strong if T has a path from x to y for every choice of distinct x, y ≡ V. We prove that every k-hypertournament on n (k) vertices has a Hamiltonian path (an extension of Redeis theorem on tournaments) and every strong k-hypertournament with n (k + 1) vertices has a Hamiltonian cycle (an extension of Camions theorem on tournaments). Despite the last result, it is shown that the Hamiltonian cycle problem remains polynomial time solvable only for k ≤ 3 and becomes NP-complete for every fixed integer k ≥ 4. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 277–286, 1997     

On The Number Of Sets Of Cycle Lengths

A set S of integers is called a cycle set on {1, 2, . . .,n} if there exists a graph G on n vertices such that the set of lengths of cycles in G is S. Erds conjectured that the number of cycle sets on {1, 2, . . .,n} is o(2 ⁿ ). In this paper, we verify this conjecture by proving that there exists an absolute constant c 0.1 such that the number of cycle sets on {1, 2, . . .,n} is .