The Primitive Sharp Permutation Groups of Twisted Wreath Type

A permutation group G ≤ Sym(X) on a finite set X is sharp if |G|=∏ _l?L(G)(|X| ? l), where L(G) = {|fix(g)| | 1 ≠ g ? G}. We show that no finite primitive permutation groups of twisted wreath type are sharp.     

On B(n,k) 2-groups

A finite group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j |1 ≤ i, j ≤ n}| ≤k. In this article, we give characterizations of the B(5, 19) 2-groups, and the B(6, k) 2-groups for 21 ≤ k ≤ 28.     

On B(4, 13) 2-Groups

A group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j  | 1 ≤ i, j ≤ n}| ≤k. In this article, we give a complete characterization of B(4, 13) 2-groups, and then obtain a complete characterization of B(4, 13) groups.     

Real Zeros of Algebraic Polynomials with Dependent Random Coefficients

The expected number of real zeros of polynomials a ₀ + a ₁ x + a ₂ x ² +…+a _n?1 x ^n?1 with random coefficients is well studied. For n large and for the normal zero mean independent coefficients, irrespective of the distribution of coefficients, this expected number is known to be asymptotic to (2/π)log n. For the dependent cases studied so far it is shown that this asymptotic value remains O(log n). In this article, we show that when cov(a _i , a _j ) = 1 ? |i ? j|/n, for i = 0,…, n ? 1 and j = 0,…, n ? 1, the above expected number of real zeros reduces significantly to O(log n)^1/2.     

Strict Dead-End Elements in Free Soluble Groups

Let G be a group generated by a finite set A. An element g ∈ G is a strict dead end of depth k (with respect to A) if |g|>|ga ₁|>|ga ₁ a ₂|>···>|ga ₁ a ₂… a _k | for any a ₁, a ₂,…, a _k  ∈ A ^±1 such that the word a ₁ a ₂… a _k is freely irreducible. (Here |g| is the distance from g to the identity in the Cayley graph of G.) We show that in finitely generated free soluble groups of degree d ≥ 2 there exist strict dead elements of depth k = k(d), which grows exponentially with respect to d.     

A note on bound for norms of Cauchy–Hankel matrices

We determine bounds for the spectral and ??_p norm of Cauchy–Hankel matrices of the form H_n=[1/(g+h(i+j))]ⁿ_i,j=1≡ ([1/(g+kh)]ⁿ_i,j=1), k=0, 1,…, n –1, where k is defined by i+j=k (mod n). Copyright © 2002 John Wiley & Sons, Ltd.     

Mutually orthogonal graph squares

A decomposition ??={G₁, G₂,…,G_s} of a graph G is a partition of the edge set of G into edge‐disjoint subgraphs G₁, G₂,…,G_s. If G_i?H for all i∈{1, 2, …, s}, then ?? is a decomposition of G by H. Two decompositions ??={G₁, G₂, …, G_n} and ?={F₁, F₂,…,F_n} of the complete bipartite graph K_n,n are orthogonal if |E(G_i)∩E(F_j)|=1 for all i,j∈{1, 2, …, n}. A set of decompositions {??₁, ??₂, …, ??_k} of K_{n, n} is a set of k mutually orthogonal graph squares (MOGS) if ??_i and ??_j are orthogonal for all i, j∈{1, 2, …, k} and i≠j. For any bipartite graph G with n edges, N(n, G) denotes the maximum number k in a largest possible set {??₁, ??₂, …, ??_k} of MOGS of K_{n, n} by G. El‐Shanawany conjectured that if p is a prime number, then N(p, P_{p+ 1})=p, where P_{p+ 1} is the path on p+ 1 vertices. In this article, we prove this conjecture. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 369–373, 2009     

Multicommodity flows in graphs

Suppose that G is a graph, and (s_i,t_i) (1≤i≤k) are pairs of vertices; and that each edge has a integer-valued capacity (≥0), and that q_i≥0 (1≤i≤k) are integer-valued demands. When is there a flow for each i, between s_i and t_i and of value q_i, such that the total flow through each edge does not exceed its capacity? Ford and Fulkerson solved this when k=1, and Hu when k=2. We solve it for general values of k, when G is planar and can be drawn so that s₁,…, s_l, t₁, …, t_l,…,t_l are all on the boundary of a face and s_l+1, …,S_k, t_l+1,…,t_k are all on the boundary of the infinite face or when t₁=?=t_l and G is planar and can be drawn so that s_l+1,…,s_k, t₁,…,t_k are all on the boundary of the infinite face. This extends a theorem of Okamura and Seymour.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

Depth of Initial Ideals of Normal Edge Rings

Let G be a finite graph on the vertex set [d] = {1,…, d} with the edges e ₁,…, e _n and K[t] = K[t ₁,…, t _d ] the polynomial ring in d variables over a field K. The edge ring of G is the semigroup ring K[G] which is generated by those monomials t ^e  = t _i t _j such that e = {i, j} is an edge of G. Let K[x] = K[x ₁,…, x _n ] be the polynomial ring in n variables over K, and define the surjective homomorphism π: K[x] → K[G] by setting π(x _i ) = t ^{e _i} for i = 1,…, n. The toric ideal I _G of G is the kernel of π. It will be proved that, given integers f and d with 6 ≤ f ≤ d, there exists a finite connected nonbipartite graph G on [d] together with a reverse lexicographic order <_rev on K[x] and a lexicographic order <_lex on K[x] such that (i) K[G] is normal with Krull-dim K[G] = d, (ii) depth K[x]/in_<rev (I _G ) = f and K[x]/in_<lex (I _G ) is Cohen–Macaulay, where in_<rev (I _G ) (resp., in_<lex (I _G )) is the initial ideal of I _G with respect to <_rev (resp., <_lex) and where depth K[x]/in_<rev (I _G ) is the depth of K[x]/in_<rev (I _G ).     

Super-π-Brauer Characters and Super-π-Regular Classes

Supercharacter theories for an arbitrary finite group were developed by Diaconis and Isaacs. Let G* denote the set of all π-regular elements of G. Set I^π(G) = {χ* | χ ∈Irr(G) and χ* ≠ α* + β* for characters α, β of G}, where χ* means the restriction of χ to G*. In this paper, we consider the partitions of I^π(G) and G* for a π-separable group G. We obtain some results which generalize those of Diaconis and Isaacs.     

Edge-disjoint paths and cycles in n-edge-connected graphs

We consider finite undirected loopless graphs G in which multiple edges are possible. For integers k,l ≥ 0 let g(k, l) be the minimal n ≥ 0 with the following property: If G is an n-edge-connected graph, s₁, ?,s_k, t₁, ?,t_k are vertices of G, and f₁, ?,f_l, g₁, ?,g_l, are pairwise distinct edges of G, then for each i = 1, ?, k there exists a path P_i in G, connecting s_i and t_i and for each i = 1, ?,l there exists a cycle C_i in G containing f_i and g_i such that P₁, ?,P_k, C₁, ?, C_l are pairwise edge-disjoint. We give upper and lower bounds for g(k, l).     

Irreducibility Criterion Over Finite Fields

The aim of this article is to prove the irreducibility of the polynomial Λ(Y) = Y ^d  + λ _d?1 Y ^d?1 + … + λ₀ over 𝔽 _q [X] where λ _i ∈ 𝔽 _q [X] and deg λ _d?1 > deg λ _i for each i ≠ d ? 1. We discuss in particular connections between the irreducible polynomials Λ and the number of Pisot elements in the case of formal power series.     

Some results on λ‐designs with two block sizes

A λ‐design is a family ?? = {B₁, B₂, …, B_v} of subsets of X = {1, 2, …, v} such that |B_i∩B_j| = λ for all i≠jand not all B_i are of the same size. The only known example of λ‐designs (called type‐1 designs) are those obtained from symmetric designs by a certain complementation procedure. Ryser [J Algebra 10 (1968), 246–261] and Woodall [Proc London Math Soc 20 (1970), 669–687] independently conjectured that all λ‐designs are type‐1. Let g = gcd(r ? 1, r^* ? 1), where rand r^* are the two replication numbers. Ionin and Shrikhande [J Combin Comput 22 (1996), 135–142; J Combin Theory Ser A 74 (1996), 100–114] showed that λ‐designs with g = 1, 2, 3, 4 are type‐1 and that the Ryser–Woodall conjecture is true for λ‐designs on p + 1, 2p + 1, 3p + 1, 4p + 1 points, where pis a prime. Hein and Ionin [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 145–156] proved corresponding results for g = 5 and Fiala [Codes and Designs—Proceedings of Conference honoring Prof. D. K. Ray‐Chaudhuri on the occasion of his 65th birthday, Ohio State University Mathematical Research Institute Publications, 10, Walter de Gruyter, Berlin, 2002, pp. 109–124; Ars Combin 68 (2003), 17–32; Ars Combin, to appear] for g = 6, 7, and 8. In this article, we consider λ designs with exactly two block sizes. We show that in this case, the conjecture is true for g = 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, and for g = 10, 14, 18, 22 with v≠4λ ? 1. We also give two results on such λ‐designs on v = 9p + 1 and 12p + 1 points, where pis a prime. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:95‐110, 2011     

Multiple positive solutions of four point boundary value problems for finite difference equations†

In this paper, we consider the following second-order four-point boundary-value problems Δ² u(k ? 1)+f(k,u(k), Δu(k)) = 0,k ∈ {1,2,…,T}, u(0) = au(l ₁), u(T+1) = bu(l ₂). We give conditions on f to ensure the existence of at least three positive solutions of the given problem by applying a new fixed-point theorem of functional type in a cone. The emphasis is put on the nonlinear term involved with the first-order difference.     

A generalization of the ray-chaudhuri-wilson theorem

Let K = {k₁,…,k_r} and L = {l₁,…,l_s} be two sets of non-negative integers and assume k_i > l_j for every i,j. Let F be an L-intersecting family of subsets of a set of n elements. Assume the size of every set in F is a number from K. We conjecture that |F| ? (ⁿ_s). We prove that our conjecturer is true for any K. (with min k_i ? s) when L = {0,1,…,s ? 1}. We also show that for any K and any L, (with min k_i > max l_j) CALLING STATEMENT : © 1995 John Wiley & Sons, Inc.     

Orthogonal factorizations of graphs

Let G be a graph with vertex set V(G) and edge set E(G). Let k₁, k₂,…,k_m be positive integers. It is proved in this study that every [0,k₁+…+k_m?m+1]‐graph G has a [0, k_i]₁^m‐factorization orthogonal to any given subgraph H with m edges. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 267–276, 2002