Toughness and the existence ofk-factors. II

In a paper with the same title [3], we proved Chvátal's conjecture thatk-tough graphs havek-factors if they satisfy trivial necessary conditions. In this paper, we prove the following stronger result: Suppose|V(G)| k + 1,k |V(G)| even, and|S| k w(G – S) – 7/8k ifw(G – S) 2, wherew(G – S) is the number of connected components ofG – S. ThenG has ak-factor.     

A sandwich theorem and Hyers—Ulam stability of affine functions

It is shown that two real functionsf andg, defined on a real intervalI, satisfy the inequalitiesf(x + (1 – )y) g(x) + (1 – )g(y) andg(x + (1 – )y) f(x) + (1 – )f(y) for allx, y I and [0, 1], iff there exists an affine functionh: I such thatf h g. As a consequence we obtain a stability result of Hyers—Ulam type for affine functions.     

Rates of convergence for the stability of large order statistics

Forr1 and eachnr, letM _nr be therth largest ofX ₁,X ₂, ...,X _n , where {X _n ,n1} is an i.i.d. sequence. Necessary and sufficient conditions are presented for the convergence of for all >0 and some –1, where {a _n } is a real sequence. Furthermore, it is shown that this series converges for all >–1, allr1 and all >0 if it converges for some >–1, somer1 and all >0.     

On the number of nowhere zero points in linear mappings

LetA be a nonsingularn byn matrix over the finite fieldGF _q ,k=n/2,q=p ^a ,a1, wherep is prime. LetP(A,q) denote the number of vectorsx in (GF _q ) ⁿ such that bothx andAx have no zero component. We prove that forn2, and ,P(A,q)[(q–1)(q–3)] ^k (q–2) ^n–2k and describe all matricesA for which the equality holds. We also prove that the result conjectured in [1], namely thatP(A,q)1, is true for allqn+23 orqn+14.     

Triangles in arrangements of lines

Givenn lines in the real projective plane, Grünbaum conjectures that, for n16, the numberp ₃ of triangular regions determined by the lines is at most 1/3n(n–1). We show that ifn7 thenp ₃ 8/21n(n–1)+2/7, we also point out that if no vertex is a point of intersection of exactly three of the lines, thenp ₃1/3n(n–1).Professor Gu died while on a visit to Poland in April 1997     

Covering a Finite Abelian Group by Subset Sums

Let G be an abelian group of order n. The critical number c(G) of G is the smallest s such that the subset sums set (S) covers all G for eachs ubset SG\{0} of cardinality |S|s. It has been recently proved that, if p is the smallest prime dividing n and n/p is composite, then c(G)=|G|/p+p–2, thus establishing a conjecture of Diderrich.We characterize the critical sets with |S|=|G|/p+p–3 and (S)=G, where p3 is the smallest prime dividing n, n/p is composite and n7p²+3p.We also extend a result of Diderrichan d Mann by proving that, for n67, |S|n/3+2 and S=G imply (S)=G. Sets of cardinality for which (S) =G are also characterized when n183, the smallest prime p dividing n is odd and n/p is composite. Finally we obtain a necessary and sufficient condition for the equality (G)=G to hold when |S|n/(p+2)+p, where p5, n/p is composite and n15p².* Work partially supported by the Spanish Research Council under grant TIC2000-1017 Work partially supported by the Catalan Research Council under grant 2000SGR00079     

Complete stability of large order statistics

Fix an integerr1. For eachnr, letM _nr be the rth largest ofX ₁,...,X _n, where {X _n,n1} is a sequence of i.i.d. random variables. Necessary and sufficient conditions are given for the convergence of _n=r n P[|M _nr /a _n –1|<] for every >0, where {a _n} is a real sequence and –1. Moreover, it is shown that if this series converges for somer1 and some >–1, then it converges for everyr1 and every >–1.     

Graphs S(n, k) and a Variant of the Tower of Hanoi Problem

For any n 1 and any k 1, a graph S(n, k) is introduced. Vertices of S(n, k) are n-tuples over {1, 2,. . . k} and two n-tuples are adjacent if they are in a certain relation. These graphs are graphs of a particular variant of the Tower of Hanoi problem. Namely, the graphs S(n, 3) are isomorphic to the graphs of the Tower of Hanoi problem. It is proved that there are at most two shortest paths between any two vertices of S(n, k). Together with a formula for the distance, this result is used to compute the distance between two vertices in O(n) time. It is also shown that for k 3, the graphs S(n, k) are Hamiltonian.     

Two vertex-disjoint cycles in a graph

LetG be a graph of ordern 6 with minimum degree at least (n + 1)/2. Then, for any two integerss andt withs 3,t 3 ands + t n, G contains two vertex-disjoint cycles of lengthss andt, respectively, unless thatn, s andt are odd andG is isomorphic toK _{(n–1)/2,(n–1)/2} + K₁. We also show that ifG is a graph of ordern 8 withn even and minimum degree at leastn/2, thenG contains two vertex-disjoint cycles with any given even lengths provided that the sum of the two lengths is at mostn.     

On the relations between infinitesimal bendings of different orders

It is established that if a surface has only one nontrivial independent field of first order infinitesimal bendings, then rigidity of order n 3 implies rigidity of any order m n, in particular, nondeformability that is analytic in parameter. All the considerations are carried out in class C ¹.In passing, a new approach to the determination of infinitesimal bendings of higher order is given. Translated from Ukrainskii Geometricheskii Sbornik, No. 35, pp. 118–124, 1992.     

A class of periodic Jacobi-Perron Algorithms in pure algebraic number fields of degree n≥3

The author obtains the periodicity of the Jacobi-Perron algorithm of (,...,^n–1) where ⁿ=(Dⁿ–d)/Vⁿ, with D, d,V N^*=1,2,..., d|D, D and d congruent to +1(mod V^n–1) and D(n–1)d(V+1)/2+1. The case V=1 has been studied by L. Bernstein and the proof for arbitrary V follows exactly the same pattern. Secondary results are then obtained from the main theorem.     

Quadrilaterals and pentagons in arrangements of lines

Let p _k denote the number of k-sided faces in an arrangement of n5 lines in the real projective plane. B. Grünbaum has shown that p ₄1/2n(n–3) and has conjectured that equality can occur only for simple arrangements. We prove this conjecture here. We also show that 4p ₄+5p ₅3n holds for every simple arrangement of n4 lines. This latter result is a strengthening of a theorem of T. O. Strommer.     

Two-sided polynomial approximation of functions

Conditions are established when the collocation polynomials P_m(x) and P_M(x), m M, constructed respectively using the system of nodes x_j of multiplicities a_j 1, j = O,, n, and the system of nodes x_-r,,x_o,,x_n,,x_n+r1, r O, r₁ O, of multiplicities a_-r,,(a_o + y_o),,(a_n + y_n),,a_n+r1, a_j + y_j 1, are two sided-approximations of the function f on the intervals , x_j[, j = O,...,n + 1, and on unions of any number of these intervals. In this case, the polynomials P_m (x), P_M ^(l) (x) with l a_j are two-sided approximations of the function f⁽¹⁾ in the neighborhood of the node x_j and the integrals of the polynomials P_m(x), P_M(x) over D_j are two-sided approximations of the integral of the function f (over D_j). If the multiplicities a_j a_j + y_j of the nodes x_j are even, then this is also true for integrals over the set _j= _µ ^k D_j µ 1, k n. It is shown that noncollocation polynomials (Fourier polynomials, etc.) do not have these properties.Kiev University. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 67, pp. 31–37, 1989.     

A finite characterization ofK-matrices in dimensions less than four

The class of realn × n matricesM, known asK-matrices, for which the linear complementarity problemw – Mz = q, w 0, z 0, w ^T z =0 has a solution wheneverw – Mz =q, w 0, z 0 has a solution is characterized for dimensionsn <4. The characterization is finite and practical. Several necessary conditions, sufficient conditions, and counterexamples pertaining toK-matrices are also given. A finite characterization of completelyK-matrices (K-matrices all of whose principal submatrices are alsoK-matrices) is proved for dimensions <4.Partially supported by NSF Grant MCS-8207217.Research partially supported by NSF Grant No. ECS-8401081.     

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.)     

On a new class of multiplicative pseudo-random number generators

In the computing literature, there are few detailed analytical studies of the global statistical characteristics of a class of multiplicative pseudo-random number generators.We comment briefly on normal numbers and study analytically the approximately uniform discrete distribution or (j,)-normality in the sense of Besicovitch for complete periods of fractional parts {x _{0 1} ⁱ /p} on [0, 1] fori=0, 1,..., (p–1)p^–1–1, i.e. in current terminology, generators given byx _{n+1 1} x _n mod p wheren=0, 1,..., (p–1)p ^–1–1,p is any odd prime, (x ₀,p)=1, ₁ is a primitive root modp ², and 1 is any positive integer.We derive the expectationsE(X, ),E(X ², ),E(X _nX_n+k); the varianceV(X, ), and the serial correlation coefficient k. By means of Dedekind sums and some results of H. Rademacher, we investigate the asymptotic properties of k for various lagsk and integers 1 and give numerical illustrations. For the frequently used case =1, we find comparable results to estimates of Coveyou and Jansson as well as a mathematical demonstration of a so-called rule of thumb related to the choice of ₁ for small k.Due to the number of parameters in this class of generators, it may be possible to obtain increased control over the statistical behavior of these pseudo-random sequences both analytically as well as computationally.     

On the chromatic uniqueness of the graphW(n,n − 2, k)

This paper shows that the graphW(n, n – 2, k) is chromatically unique for any even integern 6 and any integerk 1.     

Maximal subgroups of symmetric groups defined on projective spaces over finite fields

Let PL(n, q) be a complete projective group of semilinear transformations of the projective space P(n–1, q) of projective degree n–l over a finite field of q elements; we consider the group in its natural 2-transitive representation as a subgroup of the symmetric group S(P*(n–1, q)) on the setp*(n–1),q=p(n–1,q)/{O}. In the present note we show that for arbitrary n satisfying the inequality n>4[(qⁿ–1)/(q^n–1–1)] [in particular, for n>4(q +l)] and for an arbitrary substitutiong s (p*(n–1,q))pL(n,q) the group PL(n,q), g contains the alternating group A(P* (n–1,q)). Forq=2, 3 this result is extended to all n3.Translated from Matematicheskie Zametki, Vol. 16, No. 1, pp. 91–100, July, 1974.The author expresses his sincere thanks to M. M. Glukhov for his interest in his work.     

Decision-procedures for invariant properties of short algorithms

For a class of algorithms R satisfying sufficiently general conditions and an enumeration of the algorithms of this class, it is proved that if the algorithm from R with code m in this enumeration algorithmically decides a property, nontrivial to N₁ and invariant (with respect to extensional equality) up to N, then for N max (t²(c)t⁵(N₁, t²(a)) one has m t^–3(N), where the constantsa, c and the function t are indicated in the text of the paper, t^–3(N) is used instead of t^–1(t^–1(t^–1(N))), and finally, t^–1(x)=yx[t(y)x]. For natural enumerations the constantsa, c are not large, and the function t does not grow too rapidly. From the result obtained also follows a generalization of a theorem of Rice in a form close to that proved in [2].Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 88, pp. 73–76, 1979.In conclusion, the author thanks the participants in the Leningrad seminar on mathematical logic for valuable comments.     

The tree number of a graph with a given girth

A family of subtrees of a graphG whose edge sets form a partition of the edge set ofG is called atree decomposition ofG. The minimum number of trees in a tree decomposition ofG is called thetree number ofG and is denoted by(G). It is known that ifG is connected then(G) |G|/2. In this paper we show that ifG is connected and has girthg 5 then(G) |G|/g + 1. Surprisingly, the case wheng = 4 seems to be more difficult. We conjecture that in this case(G) |G|/4 + 1 and show a wide class of graphs that satisfy it. Also, some special graphs like complete bipartite graphs andn-dimensional cubes, for which we determine their tree numbers, satisfy it. In the general case we prove the weaker inequality(G) (|G| – 1)/3 + 1.