On the Diophantine Equation x+q=y

In this paper it has been proved that if q is an odd prime, q?7 (mod 8), n is an odd integer ?5, n is not a multiple of 3 and (h,n)=1, where h is the class number of the filed Q(√−q), then the diophantine equation x²+q^2k+1=yⁿ has exactly two families of solutions (q,n,k,x,y).     

The existence and uniqueness of strong kings in tournaments

A king x in a tournament T is a player who beats any other player y directly (i.e., x→y) or indirectly through a third player z (i.e., x→z and z→y). For x,y∈V(T), let b(x,y) denote the number of third players through which x beats y indirectly. Then, a king x is strong if the following condition is fulfilled: b(x,y)>b(y,x) whenever y→x. In this paper, a result shows that for a tournament on n players there exist exactly k strong kings, 1?k?n, with the following exceptions: k=n-1 when n is odd and k=n when n is even. Moreover, we completely determine the uniqueness of tournaments.     

The algebraic structure of the set of solutions to the Thue equation

Let Fn be a binary form with integral coefficients of degree n?2, let d denote the greatest common divisor of all non-zero coefficients of Fn, and let h?2 be an integer. We prove that if d=1 then the Thue equation (T) Fn(x,y)=h has relatively few solutions: if A is a subset of the set T(Fn,h) of all solutions to (T), with r:=card(A)?n+1, then

(#)

h divides the numberΔ(A):=_∏1?k<l?rδ(ξk,ξl),

where ξk=〈xk,yk〉∈A, 1?k?r, and δ(ξk,ξl)=xkyl−xlyk. As a corollary we obtain that if h is a prime number then, under weak assumptions on Fn, there is a partition of T(Fn,h) into at most n subsets maximal with respect to condition (#).     

Some inverse results for Hill's equation

We consider Hill's equation y″+(λ−q)y=0 where q∈L¹[0,π]. We show that if l_n—the length of the n-th instability interval—is of order O(n^−(k+2)) then the real Fourier coefficients a_n^k,b_n^k of q^(k)—k-th derivative of q—are of order O(n⁻²), which implies that q^(k) is absolutely continuous almost everywhere for k=0,1,2,….     

Multiple positive solutions to a singular boundary value problem for a superlinear Emden-Fowler equation

A multiplicity result for the singular ordinary differential equation y^″+λx⁻²yσ=0, posed in the interval (0,1), with the boundary conditions y(0)=0 and y(1)=γ, where σ>1, λ>0 and γ?0 are real parameters, is presented. Using a logarithmic transformation and an integral equation method, we show that there exists Σ^?∈(0,σ/2] such that a solution to the above problem is possible if and only if λγσ−1?Σ^?. For 0<λγσ−1<Σ^?, there are multiple positive solutions, while if γ=(λ⁻¹Σ^?)^1/(σ−1) the problem has a unique positive solution which is monotonic increasing. The asymptotic behavior of y(x) as x→⁰⁺ is also given, which allows us to establish the absence of positive solution to the singular Dirichlet elliptic problem −Δu=d⁻²(x)uσ in Ω, where Ω⊂RN, N?2, is a smooth bounded domain and d(x)=dist(x,∂Ω).     

Uniqueness and existence for nth-order right focal boundary value problems

Assuming f is bounded and solutions to the linearized equation are unique, the uniqueness and existence of solutions is established for solutions of the equation y⁽ⁿ⁾ = f(t,y,y′,…,y⁽ⁿ⁻¹⁾) subject to the right focal boundary conditions.     

Existence and uniqueness of nonnegative solutions for a boundary blow-up problem

Assume that Ω is a bounded domain in RN (N?3) with smooth boundary ∂Ω. In this work, we study existence and uniqueness of blow-up solutions for the problem −Δp(u)+c(x)|∇u|^p−1+F(x,u)=0 in Ω, where 2?p. Under some conditions related to the function F, we give a sufficient condition for existence and nonexistence of nonnegative blow-up solutions. We study also the uniqueness of these solutions.     

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.     

Higher-order recurrences for Bernoulli numbers

Euler's well-known nonlinear relation for Bernoulli numbers, which can be written in symbolic notation as n(B₀+B₀)=−nBn−1−(n−1)Bn, is extended to n(Bk₁+?+Bkm) for m?2 and arbitrary fixed integers k₁,…,km?0. In the general case we prove an existence theorem for Euler-type formulas, and for m=3 we obtain explicit expressions. This extends the authors' previous work for m=2.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

Topology of random clique complexes

In a seminal paper, Erd?s and Rényi identified a sharp threshold for connectivity of the random graph G(n,p). In particular, they showed that if p?logn/n then G(n,p) is almost always connected, and if p?logn/n then G(n,p) is almost always disconnected, as n→∞.The clique complexX(H) of a graph H is the simplicial complex with all complete subgraphs of H as its faces. In contrast to the zeroth homology group of X(H), which measures the number of connected components of H, the higher dimensional homology groups of X(H) do not correspond to monotone graph properties. There are nevertheless higher dimensional analogues of the Erd?s-Rényi Theorem.We study here the higher homology groups of X(G(n,p)). For k>0 we show the following. If p=n^α, with α<−1/k or α>−1/(2k+1), then the kth homology group of X(G(n,p)) is almost always vanishing, and if −1/k<α<−1/(k+1), then it is almost always nonvanishing.We also give estimates for the expected rank of homology, and exhibit explicit nontrivial classes in the nonvanishing regime. These estimates suggest that almost all d-dimensional clique complexes have only one nonvanishing dimension of homology, and we cannot rule out the possibility that they are homotopy equivalent to wedges of a spheres.     

Kinklike solutions of fourth-order differential equations with a cubic bistable nonlinearity

For the equation y ⁽⁴⁾+2y(y ²?1) = 0, we suggest an analytic construction of kinklike solutions (solutions bounded on the entire line and having finitely many zeros) in the form of rapidly convergent series in products of exponential and trigonometric functions. We show that, to within sign and shift, kinklike solutions are uniquely characterized by the tuple of integers n ₁, …, n _k (the integer parts of distances, divided by π, between the successive zeros of these solutions). The positivity of the spatial entropy indicates the existence of chaotic solutions of this equation.     

Uniqueness results for the one-dimensional p-Laplacian

This paper is concerned with positive solutions of the boundary value problem ^′(|y^′|^p−2y^′)+f(y)=0, y(−b)=0=y(b) where p>1, b is a positive parameter. Assume that f is continuous on (0,+∞), changes sign from nonpositive to positive, and f(y)/yp−1 is nondecreasing in the interval of f>0. The uniqueness results are proved using a time-mapping analysis.     

Further gossip problems

n people have distinct bits of information. They can communicate via k-party conference calls. How many such calls are needed to inform everyone of everyone else's information? Let f(n,k) be this minimum number. Then we give a simple proof that f(n,k)= [(n?k)(k?1)]+[nk] for 1?n?k², f(n,k)=2[(n?k)(k?1)] for n>k².In the 2-party case we consider the case in which certain of the calls may permit information flow in only one direction. We show that any 2n-4 call scheme that conveys everone's information to all must contain a 4-cycle, each of whose calls is “two way”, along with some other results. The method follows that of Bumby who first proved the 4-cycle conjecture.     

Divisors of the number of Latin rectangles

A k×n Latin rectangle on the symbols {1,2,…,n} is called reduced if the first row is (1,2,…,n) and the first column is T(1,2,…,k). Let Rk,n be the number of reduced k×n Latin rectangles and m=⌊n/2⌋. We prove several results giving divisors of Rk,n. For example, (k−1)! divides Rk,n when k?m and m! divides Rk,n when m<k?n. We establish a recurrence which determines the congruence class of for a range of different t. We use this to show that Rk,n≡((−1)^k−1(k−1)!)ⁿ⁻¹. In particular, this means that if n is prime, then Rk,n≡1 for 1?k?n and if n is composite then if and only if k is larger than the greatest prime divisor of n.     

The minimum spanning strong subdigraph problem is fixed parameter tractable

A digraph D is strong if it contains a directed path from x to y for every choice of vertices x,y in D. We consider the problem (MSSS) of finding the minimum number of arcs in a spanning strong subdigraph of a strong digraph. It is easy to see that every strong digraph D on n vertices contains a spanning strong subdigraph on at most 2n−2 arcs. By reformulating the MSSS problem into the equivalent problem of finding the largest positive integer k≤n−2 so that D contains a spanning strong subdigraph with at most 2n−2−k arcs, we obtain a problem which we prove is fixed parameter tractable. Namely, we prove that there exists an O(f(k)n^c) algorithm for deciding whether a given strong digraph D on n vertices contains a spanning strong subdigraph with at most 2n−2−k arcs.We furthermore prove that if k≥1 and D has no cut vertex then it has a kernel of order at most (2k−1)². We finally discuss related problems and conjectures.     

On shortest crucial words avoiding abelian powers

Let k≥2 be an integer. An abeliankth power is a word of the form X₁X₂?X_k where X_i is a permutation of X₁ for 2≤i≤k. A word W is said to be crucial with respect to abelian kth powers if W avoids abelian kth powers, but Wx ends with an abelian kth power for any letter x occurring in W.Evdokimov and Kitaev (2004) [2] have shown that the shortest length of a crucial word on n letters avoiding abelian squares is 4n−7 for n≥3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9n−13 for n≥5. They have also conjectured that for any k≥4 and sufficiently large n, the shortest length of a crucial word on n letters avoiding abelian kth powers, denoted by ?_k(n), is k²n−(k²+k+1). This is currently the best known upper bound for ?_k(n), and the best known lower bound, provided in Glen et al., is 3kn−(4k+1) for n≥5 and k≥4. In this note, we improve this lower bound by proving that for n≥2k−1, ?_k(n)≥k²n−(2k³−3k²+k+1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing n.     

On the uniqueness of the graphs G(n, k) of the Johnson schemes

T. A. Dowling (J. Combin. Theory6 (1969), 251–263) proved the uniqueness of the graphs G(n, k) of the Johnson schemes for n > 2k(k ? 1) + 4. We improve this result by showing the uniqueness of G(n, k) for n > 4k.