The Erdős–Pósa Property For Long Circuits

We show that, for every l, the family of circuits of length at least l satisfies the Erdős–Pósa property, with f(k)=13l(k−1)(k−2)+(2l+3)(k−1), thereby sharpening a result of C. Thomassen. We obtain as a corollary that graphs without k disjoint circuits of length l or more have tree-width O(lk²).     

On sums related to the numerator of generating functions for the <Emphasis Type="Italic">k</Emphasis>th power of Fibonacci numbers on sums related to the numerator of generating functions for the <Emphasis Type="Italic">k</Emphasis>th power of Fibonacci numbers

New results about some sums s _n (k, l) of products of the Lucas numbers, which are of similar type as the sums in [SEIBERT, J.—TROJOVSK Y, P.: On multiple sums of products of Lucas numbers, J. Integer Seq. 10 (2007), Article 07.4.5], and sums σ(k) = $ \sum\limits_{l = 0}^{\tfrac{{k - 1}} {2}} {(_l^k )F_k - 2l^S n(k,l)} $ \sum\limits_{l = 0}^{\tfrac{{k - 1}} {2}} {(_l^k )F_k - 2l^S n(k,l)} are derived. These sums are related to the numerator of generating function for the kth powers of the Fibonacci numbers. s _n (k, l) and σ(k) are expressed as the sum of the binomial and the Fibonomial coefficients. Proofs of these formulas are based on a special inverse formulas.     

Cycles intersecting a prescribed vertex set

A graph is said to have property P(k,l)(k ? l) if for any X ∈ (^G_k) there exists a cycle such that |X ∩ V(C)| = l. Obviously an n-connected graph (n ? 2) satisfies P(n,n). In this paper, we study parameters k and l such that every n-connected graph satisfies P(k,l). We show that for r = 1 or 2 every n-connected graph satisfies P(n + r,n). For r = 3, there are infinitely many 3-connected graphs that do not satisfy P(6,3). However, if n ? max{3,(2r ?1)(r + 1)}, then every n-connected graph satisfies P(n + r,n).     

k-Weakly almost convex groups and π 1 ∞ \tilde M^3

We extend Cannon's notion ofk-almost convex groups which requires that for two pointsx, y on then-sphere in the Cayley graph which can be joined by a pathl ₁ of length k, there is a second pathl ₂ in then-ball, joiningx andy, of bounded length N(k). Ourk-weakly almost convexity relaxes this condition by requiring only thatl ₁ l ₂ bounds a disk of area C ₁(k)n ^{1 - (k)} +C ₂(k). IfM ³ is a closed 3-manifold with 3-weakly almost convex fundamental group, then ₁ .     

On an asymmetric divisor problem with congruence conditions

For fixed positive integersab, natural numbersl ₁k ₁,l ₂k ₂ andn, denote withd _a,b (l ₁,k ₁;l ₂,k ₂;n) the number of all (,)N² with ^{a b} =n,l ₁(modk ₁),l ₂(modk ₂). In the present paper we establish asymptotic formulas for the Dirichlet summatory function ofd _a,b (l ₁,k ₁;l ₂,k ₂;n) with both upper and lower estimates of the error term, all of them uniform in the moduli.     

Packing a convex domain with similar convex domains

Given a convex domain C and a positive integer k, inscribe k nonoverlapping convex domains into C, all of them similar to C. Denote by f(k) the maximal sum of their circumferences. In this paper it is shown, that for C square, parallelogram or triangle (1) the first increase of f(k) after k = l² occurs not later than at k = l² + 2, (2) constructions can be given, where the following lower bounds are attained for f(k) = f(l² + j):

$\text{(}\text{1}\text{c}\text{) ? l +}\text{(j ? 1)}\text{2l}\text{j}\text{odd}\text{, l? 2}$

$\text{? l +}\text{j}\text{2}\text{(l + 1) j}\text{even}\text{, l?2}$

where c denotes the circumference of C.     

On degrees of maps between Grassmannians

Let G_n,k denote the oriented grassmann manifold of orientedk-planes in ℝⁿ. It is shown that for any continuous mapf: G_n,k → G_n,k, dim G_n,k = dim G_m,l = l(m −l), the Brouwer’s degree is zero, providedl > 1,n ≠ m. Similar results for continuous mapsg: ℂG_m,l → ℂG_n,k,h: ℍG_m,l → ℍG_n,k, 1 ≤ l < k ≤ n/2, k(n — k) = l(m — l) are also obtained.     

Optimal broadcast on parallel locality models

In this paper matching upper and lower bounds for broadcast on general purpose parallel computation models that exploit network locality are proven. These models try to capture both the general purpose properties of models like the PRAM or BSP on the one hand, and to exploit network locality of special purpose models like meshes, hypercubes, etc., on the other hand. They do so by charging a cost l(|i−j|) for a communication between processors i and j, where l is a suitably chosen latency function.An upper bound T(p)=∑_i=0^loglogp2ⁱ·l(p^1/2i) on the runtime of a broadcast on a p processor H-PRAM is given, for an arbitrary latency function l(k).The main contribution of the paper is a matching lower bound, holding for all latency functions in the range from l(k)=Ω(logk/loglogk) to l(k)=O(log²k). This is not a severe restriction since for latency functions l(k)=O(logk/log¹⁺log(k)) with arbitrary >0, the runtime of the algorithm matches the trivial lower bound Ω(logp) and for l(k)=Θ(log¹⁺k) or l(k)=Θ(k), the runtime matches the other trivial lower bound Ω(l(p)). Both upper and lower bounds apply for other parallel locality models like Y-PRAM, D-BSP and E-BSP, too.     

Compositions inside a rectangle and unimodality

Let c ^k,l (n) be the number of compositions (ordered partitions) of the integer n whose Ferrers diagram fits inside a k×l rectangle. The purpose of this note is to give a simple, algebraic proof of a conjecture of Vatter that the sequence c ^k,l (0),c ^k,l (1),…,c ^k,l (kl) is unimodal. The problem of giving a combinatorial proof of this fact is discussed, but is still open.     

On Sums of Two Coprime k-th Powers(II)

For fixed k ≥ 3, let E_k(x) denote the error term of the sum ?_{n ￡ x}r_k(n)\sum_{n\le x}\rho_k(n) , where r_k(n) = ?_{n=|m|^k+|l|^k, g.c.d.(m,l)=1}\rho_k(n) = \sum_{n=|m|^k+|l|^k, g.c.d.(m,l)=1} 1. It is proved that if the Riemann hypothesis is true, then E₃(x) << x^331/1254+eE_3(x)\ll x^{331/1254+\varepsilon} , E₄(x) << x^37/184+eE_4(x)\ll x^{37/184+\varepsilon} . A short interval result is also obtained.     

Shape sensitivity analysis of stress intensity factors by Generalized J-integrals

We consider an elastic plate with the non-deformed shape Ω_Σ := Ω \ Σ, where Ω is a domain bounded by a smooth closed curve Γ and Σ ⊂ Ω is a curve with the end points {γ₁, γ₂}. If the force g is given on the part Γ_N of Γ, the displacement u is fixed on Γ_D := Γ \ Γ_N and the body force f is given in Ω, then the displacement vector u(x) = (u₁(x), u₂(x)) has unbounded derivatives (stress singularities) near γ_k, k = 1, 2    u(x) = ∑²_{k, l=1} K_l(γ_k)r^1/2_kS^C_kl(θ_k) + u_R(x)     near γ_k. Here (r_k, θ_k) denote local curvilinear polar co-ordinates near γ_k, k = 1, 2, S^C_kl (θ_k) are smooth functions defined on [−π, π] and u_R(x) ∈ {H²(near γ_k)}². The constants K_l(γ_k),   l = 1, 2, which are called the stress intensity factors at γ_k (abbr. SIFs), are important parameters in fracture mechanics. We notice that the stress intensity factors K_l(γ_k) (l = 1, 2;  k = 1, 2) are functionals K_l(γ_k) = K_l(γ_k; ℒ︁, Ω, Σ) depending on the load ℒ︁, the shape of the plate Ω and the shape of the crack Σ. We say that the crack Σ is safe, if K_l(γ_k; Ω)² + K₂(γ_k; Ω)² < RẼ. By a small change of Ω the shape Σ can change to a dangerous one, i.e. we have K₁(γ_k; Ω)² + K₂(γ_k; Ω)² ⩾ RẼ. Therefore it is important to know how K_l(γ_k) depends on the shape of Ω. For this reason, we calculate the Gâteaux derivative of K_l(γ_k) under a class of domain perturbations which includes the approximation of domains by polygonal domains and the Hadamard's parametrization Γ(τ) := {x + τϕ(x)n(x);  x ∈ Γ}, where ϕ is a function on Γ and n is the outward unit normal on Γ. The calculations are quite delicate because of the occurrence of additional stress singularities at the collision points {γ₃, γ₄} = Γ _D ∩ Γ _N. The result is derived by the combination of the weight function method and the Generalized J-integral technique (abbr. GJ-integral technique). The GJ-integrals have been proposed by the first author in order to express the variation of energy (energy release rate) by extension of a crack in a 3D-elastic body. This paper begins with the weak solution of the crack problem, the weight function representation of SIF's, GJ-integral technique and finish with the shape sensitivity analysis of SIF's. GJ-integral J_ω(u; X) is the sum of the P-integral (line integral) P_ω(u, X) and the R-integral (area integral) R_ω(u, X). With the help of the GJ-integral technique we derive an R-integral expression for the shape derivative of the potential energy which is valid for all displacement fields u ∈ H¹. Using the property that the GJ-integral vanishes for all regular fields u ∈ H² we convert the R-integral expression for the shape derivative to a P-integral expression. © 1998 B. G. Teubner Stuttgart—John Wiley & Sons, Ltd.     

Circular choosability of graphs

This paper discusses the circular version of list coloring of graphs. We give two definitions of the circular list chromatic number (or circular choosability) χ_{c, l}(G) of a graph G and prove that they are equivalent. Then we prove that for any graph G, χ_{c, l}(G) ≥ χ_l(G) ? 1. Examples are given to show that this bound is sharp in the sense that for any ? 0, there is a graph G with χ_{c, l}(G) > χ_l(G) ? 1 + ?. It is also proved that k‐degenerate graphs G have χ_{c, l}(G) ≤ 2k. This bound is also sharp: for each ? < 0, there is a k‐degenerate graph G with χ_{c, l}(G) ≥ 2k ? ?. This shows that χ_{c, l}(G) could be arbitrarily larger than χ_l(G). Finally we prove that if G has maximum degree k, then χ_{c, l}(G) ≤ k + 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 210–218, 2005     

On the stability properties of Brown's multistep multiderivative methods

Summary Brown introducedk-step methods usingl derivatives. We investigate for whichk andl the methods are stable or unstable. It is seen that to anyl the method becomes unstable fork large enough. All methods withk2(l+1) are stable. Fork=1,2,..., 18 there exists a _k such that the methods are stable for anyl _k and unstable for anyl < _k . The _k are given.     

Generalization of the fricke theorem on entire functions of finite index

We prove that, for every sequence (a _k) of complex numbers satisfying the conditions Σ(1/|a _k |) < ∞ and |a _k+1| − |a _k | ↗ ∞ (k → ∞), there exists a continuous functionl decreasing to 0 on [0, + ∞] and such thatf(z) = Π(1 −z/|a _k |) is an entire function of finitel-index.     

Random I-colorable graphs

In this article we investigate properties of the class of all l-colorable graphs on n vertices, where l = l(n) may depend on n. Let G^l_n denote a uniformly chosen element of this class, i.e., a random l-colorable graph. For a random graph G^l_n we study in particular the property of being uniquely l-colorable. We show that not only does there exist a threshold function l = l(n) for this property, but this threshold corresponds to the chromatic number of a random graph. We also prove similar results for the class of all l-colorable graphs on n vertices with m = m(n) edges.     

The Polynomial Null Solutions of a Higher Spin Dirac Operator in Two Vector Variables

The polynomial null solutions are studied of the higher spin Dirac operator Q _k,l acting on functions taking values in an irreducible representation space for Spin(m) with highest weight ${(k + \frac{1}{2},l+\frac{1}{2},\frac{1}{2},\ldots,\frac{1}{2})}The polynomial null solutions are studied of the higher spin Dirac operator Q _k,l acting on functions taking values in an irreducible representation space for Spin(m) with highest weight (k + \frac12,l+\frac12,\frac12,?,\frac12){(k + \frac{1}{2},l+\frac{1}{2},\frac{1}{2},\ldots,\frac{1}{2})}, with k,l ? \mathbb N{k,l \in \mathbb {N}} and k = l.     

Parametrization of Triangle Groups as Subgroups of PSL(2, q)

In this paper we are interested in triangle groups (j, k, l) where j = 2 and k = 3. The groups (j, k, l) can be considered as factor groups of the modular group PSL(2, Z) which has the presentation x, y : x² = y³ = 1. Since PSL(2,q) is a factor group of G^k,l,m if -1 is a quadratic residue in the finite field F_q, it is therefore worthwhile to look at (j, k, l) groups as subgroups of PSL(2, q) or PGL(2, q). Specifically, we shall find a condition in form of a polynomial for the existence of groups (2, 3, k) as subgroups of PSL(2, q) or PGL(2, q).Mathematics Subject Classification: Primary 20F05 Secondary 20G40.     

Pancyclic arcs and connectivity in tournaments

A tournament is an orientation of the edges of a complete graph. An arc is pancyclic in a tournament T if it is contained in a cycle of length l, for every 3 ≤ l ≤ |T|. Let p(T) denote the number of pancyclic arcs in a tournament T. In 4 , Moon showed that for every non‐trivial strong tournament T, p(T) ≥ 3. Actually, he proved a somewhat stronger result: for any non‐trivial strong tournament h(T) ≥ 3 where h(T) is the maximum number of pancyclic arcs contained in the same hamiltonian cycle of T. Moreover, Moon characterized the tournaments with h(T) = 3. All these tournaments are not 2‐strong. In this paper, we investigate relationship between the functions p(T) and h(T) and the connectivity of the tournament T. Let p_k(n) := min {p(T), T k‐strong tournament of order n} and h_k(n) := min{h(T), T k‐strong tournament of order n}. We conjecture that (for k ≥ 2) there exists a constant α_k> 0 such that p_k(n) ≥ α_kn and h_k(n) ≥ 2k+1. In this paper, we establish the later conjecture when k = 2. We then characterized the tournaments with h(T) = 4 and those with p(T) = 4. We also prove that for k ≥ 2, p_k(n) ≥ 2k+3. At last, we characterize the tournaments having exactly five pancyclic arcs. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 87–110, 2004     

Improper choosability of graphs and maximum average degree

Improper choosability of planar graphs has been widely studied. In particular, ?krekovski investigated the smallest integer g_k such that every planar graph of girth at least g_k is k‐improper 2‐choosable. He proved [9] that 6 ≤ g₁ ≤ 9; 5 ≤ g₂ ≤ 7; 5 ≤ g₃ ≤ 6; and ? k ≥ 4, g_k = 5. In this article, we study the greatest real M(k, l) such that every graph of maximum average degree less than M(k, l) is k‐improper l‐choosable. We prove that if l ≥ 2 then . As a corollary, we deduce that g₁ ≤ 8 and g₂ ≤ 6, and we obtain new results for graphs of higher genus. We also provide an upper bound for M(k, l). This implies that for any fixed l, . © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 181–199, 2006     

Theh−p version of the finite element method for elliptic equations of order2m

Summary The problems of elliptic partial differential equations stemming from engineering problems are usually characterized by piecewise analytic data. It has been shown in [3, 4, 5] that the solutions of the second order and fourth order equations belong to the spacesB ¹ where the weighted Sobolev norms of thek-th derivatives are bounded byCd ^k–l (k–l)!,kl, l2 whereC andd are constants independent ofk. In this case theh–p version of the finite element method leads to an exponential rate of convergence measured in the energy norm [6, 12, 13]. Theh–p version was implemented in the code PROBE¹ [18] and has been very successfully used in the industry.We will discuss in this paper the generalization of these results for problems of order2m. We will show also that the exponential rate can be achieved if the exact solution belongs to the spacesB ¹ where the weighted Sobolev norm of thek-th derivatives is bounded byCd ^k–l (k–l)!,kl=m+1, C andd are independent ofk. In addition, if the data is piecewise analytic, then in fact the exact solution belongs to the spacesB ^m+1 .Problems of this type are related obviously to many engineering problems, such as problems of plates and shells, and are also important in connection with well-known locking problems.Dedicated to Professor Ivo Babuka on the occasion of his 60^th birthdaySupported by the Air Force Office of Science Research under grant No. AFOSR-80-0277 NOETIC TECHNOLOGIES, Inc., St. Louis, MO