Relation between frobenius and 2-frobenius groups with order components of finite groups

IfG is a finite group, we define its prime graph Г(G), as follows: its vertices are the primes dividing the order ofG and two verticesp, q are joined by an edge, if there is an element inG of orderpq. We denote the set of all the connected components of the graph Г(G) by T(G)= {π_i(G), fori = 1,2, …,t(G)}, where t(G) is the number of connected components of Г(G). We also denote by π(n) the set of all primes dividingn, wheren is a natural number. Then ¦G¦ can be expressed as a product of m₁, m₂, …, m_t(G), where m_i’s are positive integers with π(m_i) = π_i. Thesem _i ’s are called the order components ofG. LetOC(G) := {m ₁,m ₂, …,m _t (G)} be the set of order components ofG. In this paper we prove that, if G is a finite group andOC(G) =OC(M), where M is a finite simple group witht(M) ≥ 2, thenG is neither Frobenius nor 2-Frobenius.     

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

Clique graphs of time graphs

A simple, finite graph G is called a time graph (equivalently, an indifference graph) if there is an injective real function f on the vertices v(G) such that v_iv_j ∈ e(G) for v_i ≠ v_j if and only if |f(v_i) ? f(v_j)| ≤ 1. A clique of a graph G is a maximal complete subgraph of G. The clique graph K(G) of a graph G is the intersection graph of the cliques of G. It will be shown that the clique graph of a time graph is a time graph, and that every time graph is the clique graph of some time graph. Denote the clique graph of a clique graph of G by K²(G), and inductively, denote K(K^m?1(G)) by K^m(G). Define the index indx(G) of a connected time graph G as the smallest integer n such that Kⁿ(G) is the trivial graph. It will be shown that the index of a time graph is equal to its diameter. Finally, bounds on the diameter of a time graph will be derived.     

Weighted rational approximation in the complex plane

Given a triple (G, W, γ) of an open bounded set G in the complex plane, a weight function W(z) which is analytic and different from zero in G, and a number γ with 0 ≤ γ ≤ 1, we consider the problem of locally uniform rational approximation of any function ƒ(z), which is analytic in G, by weighted rational functions W^m_i+n_i(z)R_mi, n_i(z)_{i = 0}^∞, where R_mi, n_i(z) = P_mi(z)/Q_ni(z) with deg P_mi ≤ m_i and deg Q_ni ≤ n_i for all i ≥ 0 and where m_i + n_i → ∞ as i → ∞ such that lim m_i/[m_i + n_i] = γ. Our main result is a necessary and sufficient condition for such an approximation to be valid. Applications of the result to various classical weights are also included.     

A construction of Gray codes inducing complete graphs

A binary Gray code G(n) of length n, is a list of all 2ⁿn-bit codewords such that successive codewords differ in only one bit position. The sequence of bit positions where the single change occurs when going to the next codeword in G(n), denoted by S(n)?s₁,s₂,…,s_2ⁿ-1, is called the transition sequence of the Gray code G(n). The graph G_G(n) induced by a Gray code G(n) has vertex set {1,2,…,n} and edge set {{s_i,s_i+1}:1?i?2ⁿ-2}. If the first and the last codeword differ only in position s_2ⁿ, the code is cyclic and we extend the graph by two more edges {s_2ⁿ-1,s_2ⁿ} and {s_2ⁿ,s₁}. We solve a problem of Wilmer and Ernst [Graphs induced by Gray codes, Discrete Math. 257 (2002) 585-598] about a construction of an n-bit Gray code inducing the complete graph K_n. The technique used to solve this problem is based on a Gray code construction due to Bakos [A. Ádám, Truth Functions and the Problem of their Realization by Two-Terminal Graphs, Akadémiai Kiadó, Budapest, 1968], and which is presented in D.E. Knuth [The Art of Computer Programming, vol. 4, Addison-Wesley as part of “fascicle” 2, USA, 2005].     

On the Attainable Order of Collocation Methods for Delay Differential Equations with Proportional Delay

To analyze the attainable order of m-stage implicit (collocation-based) Runge-Kutta methods for the delay differential equation (DDE) y′(t) = by(qt), 0 < q ≤ 1 with y(0) = 1, and the delay Volterra integral equation (DVIE) y(t) = 1 + $\tfrac{b}{q}\int {_0^{qt} }$ y(s) ds with proportional delay qt, 0 < q ≤ 1, our particular interest lies in the approximations (and their orders) at the first mesh point t = h for the collocation solution v(t) of the DDE and the iterated collocation solution u _it(t) of the DVIE to the solution y(t). Recently, H. Brunner proposed the following open problem: “For m ≤ 3, do there exist collocation points c _i = c _i(q), i = 1, 2,..., m in [0,1] such that the rational approximant v(h)is the (m, m)-Padé approximant to y(h)? If these exist, then |v(h) ? y(h)| = O(h ^2m+1) but what is the collocation polynomial M _m(t; q) = K Π _i=1 ^m (t ? c _i) of v(th), t ∈ [0, 1]?” In this paper, we solve this question affirmatively, and give the related results between the collocation solution v(t) of the DDE and the iterated collocation solution u _it(t) of the DVIE. We also answer to Brunner's second open question in the case that one collocation point is fixed at the right end point of the interval.     

Greedy F-colorings of graphs

Let G=(V,E) be a connected graph. For a symmetric, integer-valued function δ on V×V, where K is an integer constant, N₀ is the set of nonnegative integers, and Z is the set of integers, we define a C-mapping by F(u,v,m)=δ(u,v)+m−K. A coloring c of G is an F-coloring if F(u,v,|c(u)−c(v)|)?0 for every two distinct vertices u and v of G. The maximum color assigned by c to a vertex of G is the value of c, and the F-chromatic number F(G) is the minimum value among all F-colorings of G. For an ordering of the vertices of G, a greedy F-coloring c of s is defined by (1) c(v₁)=1 and (2) for each i with 1?i<n, c(v_i+1) is the smallest positive integer p such that F(v_j,v_i+1,|c(v_j)−p|)?0, for each j with 1?j?i. The greedy F-chromatic number gF(s) of s is the maximum color assigned by c to a vertex of G. The greedy F-chromatic number of G is gF(G)=min{gF(s)} over all orderings s of V. The Grundy F-chromatic number is GF(G)=max{gF(s)} over all orderings s of V. It is shown that gF(G)=F(G) for every graph G and every F-coloring defined on G. The parameters gF(G) and GF(G) are studied and compared for a special case of the C-mapping F on a connected graph G, where δ(u,v) is the distance between u and v and .     

Bounds on some van der Waerden numbers

For positive integers s and k₁,k₂,…,ks, the van der Waerden number w(k₁,k₂,…,ks;s) is the minimum integer n such that for every s-coloring of set {1,2,…,n}, with colors 1,2,…,s, there is a ki-term arithmetic progression of color i for some i. We give an asymptotic lower bound for w(k,m;2) for fixed m. We include a table of values of w(k,3;2) that are very close to this lower bound for m=3. We also give a lower bound for w(k,k,…,k;s) that slightly improves previously-known bounds. Upper bounds for w(k,4;2) and w(4,4,…,4;s) are also provided.     

A note on the conditional moments of a multivariate normal distribution confined to a convex set

Let Y be an N(μ, Σ) random variable on R^m, 1 ≤ m ≤ ∞, where Σ is positive definite. Let C be a nonempty convex set in R^m with closure $\text{C}$. Let (·,-·) be the Eculidean inner product on R^m, and let μ_c be the conditional expected value of Y given Y ∈ C. For v ∈ R^m and s ≥ 0, let β_s(v) be the expected value of |(v, Y) ? (v, μ)|^s and let γ_s(v) be the conditional expected value of |(v, Y) ? (v, μ_c)|^s given Y ∈ C. For s ≥ 1, γ_s(v) < β_s(v) if and only if $\text{C}\text{+ Σ v ≠}\text{C}$, and γ_s(v) < β_s(v) for all v ≠ 0 if and only if $\text{C}\text{+ v ≠}\text{C}$ for any v ∈ R^m such that v ≠ 0.     

Existence and comparison theorems for nonlinear diffusion systems

In this paper we prove existence, uniqueness, and regularity results for systems of nonlinear second order parabolic equations with boundary conditions of the Dirichlet, Neumann, and regular oblique derivative types. Let K(t) consist of all functions (v¹(x), v²(x),…, v^m(x)) from $\text{Ω ? R}{}^{\mathrm{n}}$ into R^m which satisfy ψⁱ(x, t) ? vⁱ(x) ? θⁱ(x, t) for all $\text{x ? Ω}\text{and}\text{1 ? i ? m}$, where ψⁱand θⁱ are extended real-valued functions on $\text{}\text{?}\text{gW × [0, T)}$. We find conditions which will ensure that a solution U(x, t) ≡ (u¹(x, t), u²(x, t),…, u^m(x, t)) which satisfies U(x, 0) ?K(0) will also satisfy U(x, t) ?K(t) for all 0 ? t < T. This result, which has some similarity to the Gronwall Inequality, is then used to prove a global existence theorem.     

Companionship and knot group representations

A companionship argument is used to give a constructive geometric proof of a key result concerning the knot homomorph problem: Given elements μ and λ in a group G, is there a knot K in S³ and a surjective representation ρ:π₁(S³−K)→G, such that ρ(m)=μ and ρ(l)=λ, where m and l are the meridian and longitude of K. The result presented here is that if for some μ that normally generates G, the pair (μ,μⁿ) is realizable, where n is the order of H₁(G;Z, then the pair (v,vⁿ) is realizable for any normal generator v.     

On moment-discretization and least-squares solutions of linear integral equations of the first kind

Let K(s, t) be a continuous function on [0, 1] × [0, 1], and let $\text{K}$ be the linear integral operator induced by the kernel K(s, t) on the space $\text{L}$₂[0, 1]. This note is concerned with moment-discretization of the problem of minimizing 6K_x?y6 in the $\text{L}$₂-norm, where y is a given continuous function. This is contrasted with the problem of least-squares solutions of the moment-discretized equation: ∝₀¹K(s_i, t) x(t) dt = y(s_i), i = 1, 2,h., n. A simple commutativity result between the operations of “moment-discretization” and “least-squares” is established. This suggests a procedure for approximating $\text{K2y}$ (where $\text{K}$² is the generalized inverse of $\text{K}$), without recourse to the normal equation $\text{K1Kx = K1y}$, that may be used in conjunction with simple numerical quadrature formulas plus collocation, or related numerical and regularization methods for least-squares solutions of linear integral equations of the first kind.     

The interval number of a complete multipartite graph

The interval number of a graph G, denoted i(G), is the least positive integer t for which G is the intersection graph of a family of sets each of which is the union of at most t closed intervals of the real line $\text{R}$. Trotter and Harary showed that the interval number of the complete bipartite graph K(m,n) is $\text{?}\text{(mn + 1)}\text{(m + n)}\text{?}$. Matthews showed that the interval number of the complete multipartite graph K(n₁,n₂,…,n_p) was the same as the interval number of K(n₁,n₂) when n₁ = n₂ = ? = n_p. Trotter and Hopkins showed that i(K(n₁,n₂,…,n_p)) ≤ 1 + i(K(n₁,n₂)) whenever p ≥ 2 and n₁≥n₂≥ ? ≥n_p. West showed that for each n ≥ 3, there exists a constant c_n so that if p ≥ c_n,n₁ = n²?n ?1, and n₂ = n₃ = ? n_p = n, then i(K(n₁,n₂,…,n_p) = 1 + i(K(n₁, n₂)). In view of these results, it is natural to consider the problem of determining those pairs (n₁,n₂) with n₁ ≥ n₂ so that i(K(n₂,…,n_p)) = i(K(n₁,n₂)) whenever p ≥ 2 and n₂ ≥ n₃ ≥ ? ≥ n_p. In this paper, we present constructions utilizing Eulerian circuits in directed graphs to show that the only exceptional pairs are (n² ? n ? 1, n) for n ≥ 3 and (7,5).     

Dirichlet series related to the Riemann zeta function

A study is made of the function H(s, z) defined by analytic continuation of the Dirichlet series H(s, z) = Σ_n=1^∞n^?sΣ_m=1ⁿm^?z, where s and z are complex variables. For each fixed z it is shown that H(s, z) exists in the entire s-plane as a meromorphic function of s, and its poles and residues are determined. Also, for each fixed s ≠ 1 it is shown that H(s, z) exists in the entire z-plane as a meromorphic function of z, and again its poles and residues are determined. Two different representations of H(s, z) are given from which a reciprocity law, H(s, z) + H(z, s) = ζ(s) ζ(z) + ζ(s + z), is deduced. For each integer q ≥ 0 the function values H(s, ?q) and H(?q, s) are expressed in terms of the Riemann zeta function. Similar results are also obtained for the Dirichlet series T(s, z) = Σ_n=1^∞n^?sΣ_m=1ⁿm^?z (m + n)^?1. Applications include identities previously obtained by Ramanujan, Williams, and Rao and Sarma.     

An approximation technique for nonlinear integral operations

Approximation results for J. S. Mac Nerney's theory of nonlinear integral operations are established. For the nonlinear product integral _xΠ^y (1 + V)P, approximations of the form Π_{i = 1}ⁿ [1 + L_q(x_i?1, x_i)]P are considered, where L₁(u, v)P = ∝_u^vVP and L_q(u, v)P = ∝_u^vV(r, s)[1 + L_q?1(s, v)]P for q = 2, 3,…. Error bounds are obtained for the difference between the product integral and the preceding product.     

Presentations of alternating semigroups

One presentation of the alternating groupA _n hasn?2 generatorss ₁,…,s_n?2 and relationss ₁ ³ =s _i ² =(s_1?1s_i)³=(s_js_k)²=1, wherei>1 and |j?k|>1. Against this backdrop, a presentation of the alternating semigroupA _n ^c )A _n is introduced: It hasn?1 generatorss ₁,…,S _n?2,e, theA _n-relations (above), and relationse ²=e, (es ₁)⁴, (es _j)²=(es _j)⁴,es _i=s _i s ₁ ^-1 es ₁, wherej>1 andi≥1.     

Nombres de ramsey dans le cas orienté

Given two directed graphs G₁, G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any partition {U₁,U₂} of the arcs of the complete symmetric directed graph K¹_n, there exists an integer i such that the partial graph generated by U_i contains G_i as a subgraph. In this article, we determine R(P?_m,D?_n) and R(D?_m,D?_n) for some values of m and n, where P?_m denotes the directed path having m vertices and D?_m is obtained from P?_m by adding an arc from the initial vertex of P?_m to the terminal vertex.     

Combinatorics of sequential dynamical systems

In this paper we study sequential dynamical systems (SDS) over words. Our main result is the classification of SDS over words for fixed graph Y and family of local maps (F_vi) by means of a novel notion of SDS equivalence. This equivalence arises from a natural group action on acyclic orientations. An SDS consists of: (a) a graph Y, (b) a family of vertex indexed Y-local maps F_vi:Kⁿ→Kⁿ, where K is a finite field and (c) a word w, i.e. a family (w₁,…,w_k), where w_j is a Y-vertex. A map F_vi(x_v1,…,x_vn) is called Y-local iff it fixes all variables x_vj≠x_vi and depends exclusively on the variables x_vj, for v_j∈B₁(v_i). The SDS-map is obtained by composing the local maps F_vi according to the word w: . Mutual dependencies of the local maps arising from their sequential application are expressed in the graph G(w,Y) having vertex set {1,…,k} (the indices of the word w) and in which r,s are adjacent iff w_s,w_r are adjacent in Y. We prove a bijection from equivalence classes of SDS-words into equivalence classes of acyclic orientations of G(w,Y). We show that within these equivalence classes the induced SDS are equivalent in the sense that their respective phase spaces are isomorphic as digraphs.