On a conjecture of Butler and Graham

Motivated by a hat guessing problem proposed by Iwasawa, Butler and Graham made the following conjecture on the existence of a certain way of marking the coordinate lines in [k] ⁿ : there exists a way to mark one point on each coordinate line in [k] ⁿ , so that every point in [k] ⁿ is marked exactly a or b times as long as the parameters (a, b, n, k) satisfies that there are nonnegative integers s and t such that s + t = k ⁿ and as + bt = nk ^n?1. In this paper we prove this conjecture for any prime number k. Moreover, we prove the conjecture for the case when a = 0 for general k.     

Some Bistar Bipartite Ramsey Numbers

For bipartite graphs G ₁, G ₂, . . . ,G _k , the bipartite Ramsey number b(G ₁, G ₂, . . . , G _k ) is the least positive integer b so that any colouring of the edges of K _b,b with k colours will result in a copy of G _i in the ith colour for some i. A tree of diameter three is called a bistar, and will be denoted by B(s, t), where s ≥ 2 and t ≥ 2 are the degrees of the two support vertices. In this paper we will obtain some exact values for b(B(s, t), B(s, t)) and b(B(s, s), B(s, s)). Furtermore, we will show that if k colours are used, with k ≥ 2 and s ≥ 2, then \({b_{k}(B(s, s)) \leq \lceil k(s - 1) + \sqrt{(s - 1)^{2}(k^{2} - k) - k(2s - 4)} \rceil}\) . Finally, we show that for s ≥ 3 and k ≥ 2, the Ramsey number \({r_{k}(B(s, s)) \leq \lceil 2k(s - 1)+ \frac{1}{2} + \frac{1}{2} \sqrt{(4k(s - 1) + 1)^{2} - 8k(2s^{2} - s - 2)} \rceil}\) .     

Commutativity theorems for s-unital rings with constraints on commutators

Let R be an associative s-unital ring with the polynomial identity \( y^{s}[x^{n},y]=\pm [x,y^{m}]x^t\) or \( y^{s}[x^{n},y]=\pm x^{t}[x,y^{m}]\) , where m, n, s and t are given non-negative integers such that m > 0 or n > 0 and m ≠ n if s = m ? 1 and t = n ? 1. Using similar methods as in our recent papers [1] and [2], we prove here the commutativity of R for various values of m, n, s and t, under appropriate constraints on torsion of commutators.     

On the difference between an integer and its m-th power mod n

For any real constants λ ₁, λ ₂ ∈ (0, 1], let $n \geqslant \max \{ [\tfrac{1} {{\lambda _1 }}],[\tfrac{1} {{\lambda _2 }}]\} $ , m ? 2 be integers. Suppose integers a ∈ [1, λ ₁ n] and b ∈ [1, λ ₂ n] satisfy the congruence b ≡ a ^m (mod n). The main purpose of this paper is to study the mean value of (a ? b)^2k for any fixed positive integer k and obtain some sharp asymptotic formulae.     

Classification of reflexible regular embeddings and self-Petrie dual regular embeddings of complete bipartite graphs

In this paper, we classify the reflexible regular orientable embeddings and the self-Petrie dual regular orientable embeddings of complete bipartite graphs. The classification shows that for any natural number n, say (p₁,p₂,…,p_k are distinct odd primes and a_i>0 for each i?1), there are t distinct reflexible regular embeddings of the complete bipartite graph K_n,n up to isomorphism, where t=1 if a=0, t=2^k if a=1, t=2^k+1 if a=2, and t=3·2^k+1 if a?3. And, there are s distinct self-Petrie dual regular embeddings of K_n,n up to isomorphism, where s=1 if a=0, s=2^k if a=1, s=2^k+1 if a=2, and s=2^k+2 if a?3.     

On the 4-power stufe of a field

Define the 4-powers ₄ (k) of a fieldk to be the least positive integers for which the equation ?1=a ₁ ⁴ +…+a _s ⁴ is solvable ink (if at all). We determines ₄ (k) whenk is a Galois field and prove some results abouts ₄ (k) whenk is an imaginary quadratic field.     

Hypercube orientations with only two in-degrees

We consider the problem of orienting the edges of the n-dimensional hypercube so only two different in-degrees a and b occur. We show that this can be done, for two specified in-degrees, if and only if obvious necessary conditions hold. Namely, we need 0?a,b?n and also there exist non-negative integers s and t so that s+t=n² and as+bt=n²n−1. This is connected to a question arising from constructing a strategy for a “hat puzzle”.     

Parity results for 9-regular partitions

Let t≥2 be an integer. We say that a partition is t-regular if none of its parts is divisible by t, and denote the number of t-regular partitions of n by b _t (n). In this paper, we establish several infinite families of congruences modulo 2 for b ₉(n). For example, we find that for all integers n≥0 and k≥0, $$b_9 \biggl(2^{6k+7}n+ \frac{2^{6k+6}-1}{3} \biggr)\equiv 0 \quad (\mathrm{mod}\ 2 ). $$      

On-Line Dimension for Posets Excluding Two Long Incomparable Chains

For a positive integer k, let k?+?k denote the poset consisting of two disjoint k-element chains, with all points of one chain incomparable with all points of the other. Bosek, Krawczyk and Szczypka showed that for each k?≥?1, there exists a constant c _k so that First Fit will use at most $c_kw^2$ chains in partitioning a poset P of width at most w, provided the poset excludes k?+?k as a subposet. This result played a key role in the recent proof by Bosek and Krawczyk that O(w ^16logw ) chains are sufficient to partition on-line a poset of width w into chains. This result was the first improvement in Kierstead’s exponential bound: (5 ^w ???1)/4 in nearly 30 years. Subsequently, Joret and Milans improved the Bosek–Krawczyk–Szczypka bound for the performance of First Fit to 8(k???1)² w, which in turn yields the modest improvement to O(w ^14logw ) for the general on-line chain partitioning result. In this paper, we show that this class of posets admits a notion of on-line dimension. Specifically, we show that when k and w are positive integers, there exists an integer t?=?t(k,w) and an on-line algorithm that will construct an on-line realizer of size t for any poset P having width at most w, provided that the poset excludes k?+?k as a subposet.     

Nilpotent and invertible values in semiprime rings with generalized derivations

Let R be a semiprime ring and F be a generalized derivation of R and n??? 1 a fixed integer. In this paper we prove the following: (1) If (F(xy) ? yx) ⁿ is either zero or invertible for all ${x,y\in R}$ , then there exists a division ring D such that either R?=?D or R?=?M ₂(D), the 2?× 2 matrix ring. (2) If R is a prime ring and I is a nonzero right ideal of R such that (F(xy) ? yx) ⁿ ?=?0 for all ${x,y \in I}$ , then [I, I]I?=?0, F(x)?=?ax?+?xb for ${a,b\in R}$ and there exist ${\alpha, \beta \in C}$ , the extended centroid of R, such that (a ? ??)I?=?0 and (b ? ??)I?=?0, moreover ((a?+?b)x ? x)I?=?0 for all ${x\in I}$ .     

On diophantine equations of the form {({\boldsymbol x}-{\boldsymbol a}_{\bf 1})({\boldsymbol x}-{\boldsymbol a}_{\bf 2}) \ldots ({\boldsymbol x}-{\boldsymbol a}_{\boldsymbol k}) + {\boldsymbol r} = {\boldsymbol y}^{ \boldsymbol n}}

Erd?s and Selfridge [3] proved that a product of consecutive integers can never be a perfect power. That is, the equation x(x?+?1)(x?+?2)...(x?+?(m???1))?=?y ⁿ has no solutions in positive integers x,m,n where m, n?>?1 and y?∈?Q. We consider the equation $$ (x-a_1)(x-a_2) \ldots (x-a_k) + r = y^n $$ where 0?≤?a ₁?<?a ₂?<???<?a _k are integers and, with r?∈?Q, n?≥?3 and we prove a finiteness theorem for the number of solutions x in Z, y in Q. Following that, we show that, more interestingly, for every nonzero integer n?>?2 and for any nonzero integer r which is not a perfect n-th power for which the equation admits solutions, k is bounded by an effective bound.     

On the reducibility of some composite polynomials over finite fields

Let g(x)?=?x ⁿ ?+?a _n-1 x ^n-1?+?. . .?+?a ₀ be an irreducible polynomial over ${\mathbb{F}_q}$ . Varshamov proved that for a?=?1 the composite polynomial g(x ^p ?ax?b) is irreducible over ${\mathbb{F}_q}$ if and only if ${{\rm Tr}_{\mathbb{F}_q/\mathbb{F}_p}(nb-a_{n-1})\neq 0}$ . In this paper, we explicitly determine the factorization of the composite polynomial for the case a?=?1 and ${{\rm Tr}_{\mathbb{F}_q/\mathbb{F}_p}(nb-a_{n-1})= 0}$ and for the case a?≠ 0, 1. A recursive construction of irreducible polynomials basing on this composition and a construction with the form ${g(x^{r^kp}-x^{r^k})}$ are also presented. Moreover, Cohen’s method of composing irreducible polynomials and linear fractions are considered, and we show a large number of irreducible polynomials can be obtained from a given irreducible polynomial of degree n provided that gcd(n, q ³ ? q)?=?1.     

A test for the existence of Gohberg-Krein representations in terms of multiparameter Wiener processes

This paper provides new necessary and sufficient conditions for a Gaussian random field to have a Gohberg-Krein representation in terms of an n-parameter Wiener process (n > 1). As an application, it demonstrates the nonexistence of a Gohberg-Krein representation of W_s,t ? stW_1,1 in terms of the two-parameter Wiener process W_s,t with (s, t) ? [0, a] × [0, b] for 0 < a < 1, 0 < b < 1.     

On linear combinations of generalized involutive matrices

Let X ^? denotes the Moore--Penrose pseudoinverse of a matrix X. We study a number of situations when (aA?+?bB)^??=?aA?+?bB provided a,?b?∈?????{0} and A, B are n?×?n complex matrices such that A ^??=?A and B ^??=?B.     

Exact solution of the hypergraph Turán problem for k-uniform linear paths

A k-uniform linear path of length ?, denoted by ? _? ^(k) , is a family of k-sets {F ₁,...,F _? such that |F _i ∩ F _i+1|=1 for each i and F _i ∩ F _bj = \(\not 0\) whenever |i?j|>1. Given a k-uniform hypergraph H and a positive integer n, the k-uniform hypergraph Turán number of H, denoted by ex _k (n, H), is the maximum number of edges in a k-uniform hypergraph \(\mathcal{F}\) on n vertices that does not contain H as a subhypergraph. With an intensive use of the delta-system method, we determine ex _k (n, P _? ^(k) exactly for all fixed ? ≥1, k≥4, and sufficiently large n. We show that $ex_k (n,\mathbb{P}_{2t + 1}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} )$ . The only extremal family consists of all the k-sets in [n] that meet some fixed set of t vertices. We also show that $ex(n,\mathbb{P}_{2t + 2}^{(k)} ) = (_{k - 1}^{n - 1} ) + (_{k - 1}^{n - 2} ) + \cdots + (_{k - 1}^{n - t} ) + (_{k - 2}^{n - t - 2} )$ , and describe the unique extremal family. Stability results on these bounds and some related results are also established.     

Zeros of polynomials embedded in an orthogonal sequence

Let $\{x_{k,n}\}_{k=1}^n$ and $\{x_{k,n+1}\}_{k=1}^{n+1}$ , n?????, be two given sets of real distinct points with x _1,n?+?1?<?x _1,n ?<?x _2,n?+?1?<?...?<?x _n,n ?<?x _n?+?1,n?+?1. Wendroff (cf. Proc Am Math Soc 12:554?C555, 1961) proved that if $p_n(x)=\displaystyle{\prod\limits_{k=1}^n(x-x_{k,n})}$ and $p_{n+1}(x)=\displaystyle \prod\limits_{k=1}^{n+1}(x-x_{k,n+1})$ then p _n and p _n?+?1 can be embedded in a non-unique infinite monic orthogonal sequence $\{p_n\}_{n=0}^{\infty}$ . We investigate the connection between the zeros of p _n?+?2 and the two coefficients b _n?+?1????? and ?? _n?+?1?>?0, which are chosen arbitrarily, that define p _n?+?2 via the three term recurrence relation $$ p_{n+2}(x)=(x-b_{n+1})p_{n+1}(x)-\lambda_{n+1}p_n(x). $$      

A contribution to the Zarankiewicz problem

Given positive integers let z(m,n,s,t) be the maximum number of ones in a (0,1) matrix of size m×n that does not contain an all ones submatrix of size s×t. We show that if s?2 and t?2, then for every k=0,…,s-2,

z(m,n,s,t)?(s-k-1)^1/tnm^1-1/t+kn+(t-1)m^1+k/t.     

On 2min-sets and 2minmax-sets with respect to certain cycles

Let [n] = {1, 2, …, n}. Suppose we have k linear orderings on [n], say <1, <2, …, <k. Let M ? [n]. Then M has a minimum for each linear ordering <i. So M has at most k minima. A set M ? [n] is called a 2min-set if it has at most two different minima in the linear orderings <1, <2, …, <k. Similarly, a set N ? [n] can have at most k minima and k maxima for any k linear orderings. A set N ? [n] is called a 2minmax-set if there exist a, b ∈ N such that all the elements in N | {a, b} lie in between a and b for every linear ordering <i. In this paper, we shall determine the sizes of 2min-sets and 2minmax-sets for certain k linear orderings.     

A uniqueness theorem for indefinite Sturm-Liouville operators

In this paper, we discuss the inverse problem for indefinite Sturm-Liouville operators on the finite interval [a, b]. For a fixed index n(n = 0, 1, 2, ··· ), given the weight function ω(x), we will show that the spectral sets {λ n (q, h a , h k )} +∞ k=1 and {λ-n (q, h b , h k )} +∞ k=1 for distinct h k are sufficient to determine the potential q(x) on the finite interval [a, b] and coefficients h a and h b of the boundary conditions.