The game of n-times nim

The following game is considered. The first player can take any number of stones, but not all the stones, from a single pile of stones. After that, each player can take at most n-times as many as the previous one. The player first unable to move loses and his opponent wins. Let f₁,f₂,… be an initial sequence of stones in increasing order, such that the second player has a winning strategy when play begins from a pile of size f_i. It is proved that there exist constants c=c(n) and k₀=k₀(n) such that f_k+1=f_k+f_k−c for all k>k₀, and lim_n→∞ c(n)/(nlogn)=1.     

Finding all essential terms of a characteristic maxpolynomial

Let us denote ab=max(a,b) and ab=a+b for and extend this pair of operations to matrices and vectors in the same way as in linear algebra. We present an O(n²(m+n log n)) algorithm for finding all essential terms of the max-algebraic characteristic polynomial of an n×n matrix over with m finite elements. In the cases when all terms are essential, this algorithm also solves the following problem: Given an n×n matrix A and k{1,…,n}, find a k×k principal submatrix of A whose assignment problem value is maximum.     

Embeddings of the base and bundle isomorphisms

Let π_i :E_i→M, i=1,2, be oriented, smooth vector bundles of rank k over a closed, oriented n-manifold with zero sections s_i :M→E_i. Suppose that U is an open neighborhood of s₁(M) in E₁ and F :U→E₂ a smooth embedding so that π₂Fs₁ :M→M is homotopic to a diffeomorphism f. We show that if k>[(n+1)/2]+1 then E₁ and the induced bundle f^*E₂ are isomorphic as oriented bundles provided that f have degree +1; the same conclusion holds if f has degree −1 except in the case where k is even and one of the bundles does not have a nowhere-zero cross-section. For n≡0(4) and [(n+1)/2]+1<kn we give examples of nonisomorphic oriented bundles E₁ and E₂ of rank k over a homotopy n-sphere with total spaces diffeomorphic with orientation preserved, but such that E₁ and f^*E₂ are not isomorphic oriented bundles. We obtain similar results and counterexamples in the more difficult limiting case where k=[(n+1)/2]+1 and M is a homotopy n-sphere.     

A reversal index for tournament matrices

Given a tournament matrix T, its reversal indexi_R(T), is the minimum k such that the reversal of the orientation of k arcs in the directed graph associated with T results in a reducible matrix. We give a formula for i_R(T) in terms of the score vector of T which generalizes a simple criterion for a tournament matrix to be irreducible. We show that i_R(T)≤[(n-1)/2] for any tournament matrix T of order n, with equality holding if and only if T is regular or almost regular, according as n is odd or even. We construct, for each k between 1 and [(n-1)/2], a tournament matrix of order n whose reversal index is k. Finally, we suggest a few problems.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

Factorizations of root-based polynomial compositions

Let denote the finite field of order q=p^r, p a prime and r a positive integer, and let f(x) and g(x) denote monic polynomials in of degrees m and n, respectively. Brawley and Carlitz (Discrete Math. 65 (1987) 115–139) introduce a general notion of root-based polynomial composition which they call the composed product and denote by fg. They prove that fg is irreducible over if and only if f and g are irreducible with gcd(m,n)=1. In this paper, we extend Brawley and Carlitz's work by examining polynomials which are composed products of irreducibles of non-coprime degrees. We give an upper bound on the number of distinct factors of fg, and we determine the possible degrees that the factors of fg can assume. We also determine when the bound on the number of factors of fg is met.     

Induced subgraphs of given sizes

We say (n, e) → (m, f), an (m, f) subgraph is forced, if every n-vertex graph of size e has an m-vertex spanned subgraph with f edges. For example, as Turán proved, (n,e)→(k,(^k₂)) for e> t_{k − 1}(n) and (n,e) (^k₂)), otherwise. We give a number of constructions showing that forced pairs are rare. Using tools of extremal graph theory we also show infinitely many positive cases. Several problems remain open.     

Embedding matrices in Hadamard matrices

It is shown that if A is any n×n matrix of zeros and ones, and if k is the smallest number not less than n which is the order of an Hadamard matrix, then A is a submatrix of an Hadamard matrix of order k².     

An extremal problem concerning matrices of 0's and 1 's

We determine the smallest number f(n,k) such that every (0,1)-matrix of order n what zero main diagonal which has at least f(n,k) 1's contains an irreducible, principal submatrix of order K. We characterize those matrices with f(n,k)?1 l's having no irreducible, principal submatrix of order k     

On determinants of nonprincipal submatrices of hermitian matrices

It is our purpose to compute the maximum value of the modulus of the determinant of an m×m nonprincipal submatrix of an n×n hermitian (or real symmetric) matrix A, in terms of m, the eigenvalues of A, and the cardinality k of the set of common row and column indices of this submatrix.     

On the degree of the inverse of an automorphism of the affine space

We study the degree of the inverse of an automorphism f of the affine n-space over a -algebra k, in terms of the degree d of f and of other data. For n = 1, we obtain a sharp upper bound for deg (f^{− 1}) in terms of d and of the nilpotency index of the ideal generated by the coefficients of f^′'. For n = 2 and arbitrary d≥ 3, we construct a (triangular) automorphism f of Jacobian one such that deg(f^{− 1}) > d. This answers a question of A. van den Essen (see [3]) and enables us to deduce that some schemes introduced by authors to study the Jacobian conjecture are not reduced. Still for n = 2, we give an upper bound for deg (f^{− 1}) when f is triangular. Finally, in the case d = 2 and any n, we complete a result of G. Meisters and C. Olech and use it to give the sharp bound for the degree of the inverse of a quadratic automorphism, with Jacobian one, of the affine 3-space.     

Stability of Periodic Orbits and Return Trajectories of Continuous Multi-valued Maps on Intervals

Let I be a compact interval of real axis R, and(I, H) be the metric space of all nonempty closed subintervals of I with the Hausdorff metric H and f : I → I be a continuous multi-valued map. Assume that Pn =(x_0, x_1,..., xn) is a return tra jectory of f and that p ∈ [min Pn, max Pn] with p ∈ f(p). In this paper, we show that if there exist k(≥ 1) centripetal point pairs of f(relative to p)in {(x_i; x_i+1) : 0 ≤ i ≤ n-1} and n = sk + r(0 ≤ r ≤ k-1), then f has an R-periodic orbit, where R = s + 1 if s is even, and R = s if s is odd and r = 0, and R = s + 2 if s is odd and r 0. Besides,we also study stability of periodic orbits of continuous multi-valued maps from I to I.     

Degrees in a digraph whose nodes are graphs

By an f-graph we mean an unlabeled graph having no vertex of degree greater than f. Let D(n, f) denote the digraph whose node set is the set of f-graphs of order n and such that there is an arc from the node corresponding to graph H to the node corresponding to the graph K if and only if K is obtainable from H by the addition of a single edge. In earlier work, algorithms were developed which produce exact results about the structure of D(n, f), nevertheless many open problems remain. For example, the computation of the order and size of D(n, f) for a number of values of n and f have been obtained. Formulas for the order and size for f = 2 have also been derived. However, no closed form formulas have been determined for the order and size of D(n, f) for any value of f. Here we focus on questions concerning the degrees of the nodes in D(n,n − 1) and comment on related questions for D(n,f) for 2 f < n − 1.     

Maximum number of edges in a critically k-connected graph

A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p²/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs.     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

On the number of edge-disjoint one factors and the existence of k-factors in complete multipartite graphs

In this paper we use Tutte's f-factor theorem and the method of amalgamations to find necessary and sufficient conditions for the existence of a k-factor in the complete multipartite graph K(p(1), …, p(n)), conditions that are reminiscent of the Erdös-Gallai conditions for the existence of simple graphs with a given degree sequence. We then use this result to investigate the maximum number of edge-disjoint 1-factors in K(p(1), …, p(n)), settling the problem in the case where this number is greater than δ - p(2), where p(1) p(2) … p(n).     

A doubly cyclic channel assignment problem

A standard model for radio channel assignment involves a set V of sites, the set {0,1,2,…} of channels, and a constraint matrix (w(u, v)) specifying minimum channel separations. An assignment f:V→{0,1,2,…} is feasible if the distance f(u) − f(v)w(u, v) for each pair of sites u and v. The aim is to find the least k such that there is a feasible assignment using only the k channels 0, 1, …, k − 1, and to find a corresponding optimal assignment.

We consider here a related problem involving also two cycles. There is a given cyclic order τ on the sites, and feasible assignments f must also satisfy f(τv) f(v) for all except one site v. Further, the channels are taken to be evenly spaced around a circle, so that if the k channels 0, 1, …, k − 1 are available then the distance between channels i and j is the minimum of ¦i − j¦ and k − ¦i − j¦. We show how to find a corresponding optimal channel assignment in O(¦V¦³) steps.     

Some Ore-type Results for Matching and Perfect Matching in <Emphasis Type="Italic">k</Emphasis>-uniform Hypergraphs

Let S₁ and S₂ be two (k-1)-subsets in a k-uniform hypergraph H. We call S₁ and S₂ strongly or middle or weakly independent if H does not contain an edge e ∈ E(H) such that S₁ ∩ e ≠∅ and S₂ ∩ e ≠∅ or e ⊆ S₁ ∪ S₂ or e ⊇ S₁ ∪ S₂, respectively. In this paper, we obtain the following results concerning these three independence. (1) For any n ≥ 2k²-k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent (k-1)-sets equal to 2n-4(k-1), contains no perfect matching; (2) Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd+(k-2)k. If the degree sum of any two middle independent (k-1)-subsets is larger than 2(d-1), then H contains a d-matching; (3) For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent (k-1)-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n.     

Gowers norms and pseudorandom measures of subsets

Let $A \subset {{\Bbb Z}_N}$, and ${f_A}(s) = \left\{ {\begin{array}{*{20}{l}}{1 - \frac{{|A|}}{N},}&{{\rm{for}}\;s \in A,}\\{ - \frac{{|A|}}{N},}&{{\rm{for}}\;s \notin A.}\end{array}} \right.$ We define the pseudorandom measure of order k of the subset A as follows, P_k(A, N) = $\begin{array}{*{20}{c}}{\max }\\D\end{array}$|$\mathop \Sigma \limits_{n \in {\mathbb{Z}_N}}$f_A(n + c₁)f_A(n + c₂) … f_A(n + c_k)|, where the maximum is taken over all D = (c₁, c₂, . . . , c_k) ∈ ${\mathbb{Z}^k}$ with 0 ≤ c₁ < c₂ < … < c_k ≤ N - 1. The subset A ⊂ ${{\mathbb{Z}_N}}$ is considered as a pseudorandom subset of degree k if P_k(A, N) is “small” in terms of N. We establish a link between the Gowers norm and our pseudorandom measure, and show that “good” pseudorandom subsets must have “small” Gowers norm. We give an example to suggest that subsets with “small” Gowers norm may have large pseudorandom measure. Finally, we prove that the pseudorandom subset of degree L(k) contains an arithmetic progression of length k, where L(k) = 2·lcm(2, 4, . . . , 2|$\frac{k}{2}$|), for k ≥ 4, and lcm(a₁, a₂, . . . , a_l) denotes the least common multiple of a₁, a₂, . . . , a_l.     

Similarity to symmetric matrices over fields which are not formally real

We show that a matrix is similar to a symmetric matrix over a field of characteristic 2 if and only if the minimum polynomial of the matrix is not the product of distinct irreducible polynomials whose splitting fields are inseparable extensions. When the field is not of characteristic 2, a known theorem is generalized by considering k, the number of elementary divisors of odd degree of the n × n A: If -1 is a sum of 2^v squares and n differs from a multiple of 2^{v + 1} by at most ±k, then A is similar to a symmetric matrix.