A Note on Directed Genera of Some Tournaments

An embedding of a digraph in an orientable surface is an embedding as the underlying graph and arcs in each region force a directed cycle. The directed genus is the minimum genus of surfaces in which the digraph can be directed embedded. Bonnington, Conder, Morton and McKenna [J. Combin. Theory Ser. B, 85(2002) 1-20] gave the problem that which tournaments on n vertices have the directed genus ?(n?3)(n?4)/12 ?, the genus of K_n. In this paper, we use the current graph method to show that there exists a tournament, which has the directed genus ?(n?3)(n?4)/12 ?, on n vertices if and only if n ≡ 3 or 7 (mod 12).     

The construction of infinite families of any κ-tight optimal and singular κ-tight optimal directed double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted great attention. A related and longtime unsolved problem is for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained (1) for any k ≥ 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(k,e,c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k ≥ 0,an infinite family of singular k-tight optimal DLN can be constructed.     

The real symmetric matrices of odd order with a P-set of maximum size

Suppose that A is a real symmetric matrix of order n. Denote by m_A(0) the nullity of A. For a nonempty subset α of {1, 2,..., n}, let A(α) be the principal submatrix of A obtained from A by deleting the rows and columns indexed by α. When m_A(α)(0) = m_A(0)+|α|, we call α a P-set of A. It is known that every P-set of A contains at most ?n/2? elements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As a first step to the full characterization of these graphs of odd order, we establish some conditions for such graphs G under which there is a real symmetric matrix A whose graph is G and contains a P-set of size (n ? 1)/2.     

Super Edge-connectivity and Zeroth-order General Randić Index for −1 ≤ <Emphasis Type="Italic">α</Emphasis> &lt; 0

Let G be a connected graph with order n, minimum degree δ = δ(G) and edge-connectivity λ = λ(G). A graph G is maximally edge-connected if λ = δ, and super edge-connected if every minimum edgecut consists of edges incident with a vertex of minimum degree. Define the zeroth-order general Randi? index \(R_\alpha ^0\left( G \right) = \sum\limits_{x \in V\left( G \right)} {d_G^\alpha \left( x \right)} \), where d_G(x) denotes the degree of the vertex x. In this paper, we present two sufficient conditions for graphs and triangle-free graphs to be super edge-connected in terms of the zeroth-order general Randi? index for ?1 ≤ α < 0, respectively.     

Critical vertices in k-connected digraphs

It is proved that every non-complete, finite digraph of connectivity number k has a fragment F containing at most k critical vertices. The following result is a direct consequence: every k-connected, finite digraph D of minimum out- and indegree at least \(2k+ m- 1\) for positive integers k, m has a subdigraph H of minimum outdegree or minimum indegree at least \(m-1\) such that \(D - x\) is k-connected for all \(x \in V(H)\). For \(m = 1\), this implies immediately the existence of a vertex of indegree or outdegree less than 2k in a k-critical, finite digraph, which was proved in Mader (J Comb Theory (B) 53:260–272, 1991).     

Linear arboricity of regular digraphs

A linear directed forest is a directed graph in which every component is a directed path.The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and P′eroche conjecture that la(D) = d + 1. In this paper, we consider the linear arboricity for complete symmetric digraphs,regular digraphs with high directed girth and random regular digraphs and we improve some wellknown results. Moreover, we propose a more precise conjecture about the linear arboricity for regular digraphs.     

A new estimate for the vertex number of an edge-regular graph

Given a connected edge-regular graph Γ with parameters (v, k, λ) and b ₁ = k ? λ ? 1, we prove that in the case k ≥ 3b ₁ ?2 either |Γ₂(u)|(k?2b ₁ + 2) < kb ₁ for every vertex u or Γ is a polygon, the edge graph of a trivalent graph without triangles that has diameter greater than 2, the icosahedral graph, the complete multipartite graph K _r×2, the 3 × 3-grid, the triangular graph T(m) with m ≤ 7, the Clebsch graph, or the Schläfli graph.     

Tensor products of complementary series of rank one Lie groups

We consider the tensor product π_α ? π_βof complementary series representations π_α and π_β of classical rank one groups SO_0(n, 1), SU(n, 1) and Sp(n, 1). We prove that there is a discrete component π_(α+β)for small parameters α and β(in our parametrization). We prove further that for SO_0(n, 1) there are finitely many complementary series of the form π_(α+β+2j,)j = 0, 1,..., k, appearing in the tensor product π_α ? π_βof two complementary series π_α and π_β, where k = k(α, β, n) depends on α, β and n.     

Homogenization of the Dirichlet problem for elliptic and parabolic systems with periodic coefficients

Let O ? R ^d be a bounded domain of class C ^1,1. Let 0 < ε - 1. In L ₂(O;C ⁿ ) we consider a positive definite strongly elliptic second-order operator B _D,ε with Dirichlet boundary condition. Its coefficients are periodic and depend on x/ε. The principal part of the operator is given in factorized form, and the operator has lower order terms. We study the behavior of the generalized resolvent (B _D,ε ? ζQ ₀(·/ε))^?1 as ε → 0. Here the matrix-valued function Q ₀ is periodic, bounded, and positive definite; ζ is a complex-valued parameter. We find approximations of the generalized resolvent in the L ₂(O;C ⁿ )-operator norm and in the norm of operators acting from L ₂(O;C ⁿ ) to the Sobolev space H ¹(O;C ⁿ ) with two-parameter error estimates (depending on ε and ζ). Approximations of the generalized resolvent are applied to the homogenization of the solution of the first initial-boundary value problem for the parabolic equation Q ₀(x/ε)? _t v _ε (x, t) = ?(B _D,ε v _ε )(x, t).     

When does the zero-one <Emphasis Type="Italic">k</Emphasis>-law fail?

The limit probabilities of the first-order properties of a random graph in the Erd?s–Rényi model G(n, n^?α), α ∈ (0, 1), are studied. A random graph G(n, n^?α) is said to obey the zero-one k-law if, given any property expressed by a formula of quantifier depth at most k, the probability of this property tends to either 0 or 1. As is known, for α = 1? 1/(2^k?1 + a/b), where a > 2^k?1, the zero-one k-law holds. Moreover, this law does not hold for b = 1 and a ≤ 2^k?1 ? 2. It is proved that the k-law also fails for b > 1 and a ≤ 2^k?1 ? (b + 1)².     

Reducing subspaces of tensor products of weighted shifts

A unilateral weighted shift A is said to be simple if its weight sequence {α_n} satisfies ▽~3(α_n~2)≠0for all n≥2.We prove that if A and B are two simple unilateral weighted shifts,then AI+IB is reducible if and only if A and B are unitarily equivalent.We also study the reducing subspaces of A~kI+IB~l and give some examples.As an application,we study the reducing subspaces of multiplication operators Mzk+αωl on function spaces.     

Ramsey numbers of cubes versus cliques

The cube graph Q _n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2 ⁿ vertices. The Ramsey number r(Q _n ;K _s ) is the minimum N such that every graph of order N contains the cube graph Q _n or an independent set of order s. In 1983, Burr and Erd?s asked whether the simple lower bound r(Q _n ;K _s )≥(s?1)(2 ⁿ ?1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.     

Bounds for the signless Laplacian energy of digraphs

Let G be a digraph with n vertices, a arcs, c ₂ directed closed walks of length 2. Let q1; q2;:::; q _n be the eigenvalues of the signless Laplacian matrix of G. The signless Laplacian energy of a digraph G is defined as E _SL (G) = \(\sum\limits_{i = 1}^n {\left| {{q_i} - \frac{a}{n}} \right|} \). In this paper, some lower and upper bounds are derived for the signless Laplacian energy of digraphs.     

On a classical theorem on the diameter and minimum degree of a graph

In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erd¨os, Pach, Pollack and Tuza.We use these bounds in order to study hyperbolic graphs(in the Gromov sense). To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H(n, δ_0) be the set of graphs G with n vertices and minimum degree δ_0, and J(n, Δ) be the set of graphs G with n vertices and maximum degree Δ. We study the four following extremal problems on graphs: a(n, δ_0) = min{δ(G) | G ∈ H(n, δ_0)}, b(n, δ_0) = max{δ(G) |G ∈ H(n, δ_0)}, α(n, Δ) = min{δ(G) | G ∈ J(n, Δ)} and β(n, Δ) = max{δ(G) | G ∈ J(n, Δ)}. In particular, we obtain bounds for b(n, δ_0) and we compute the precise value of a(n, δ_0), α(n, Δ) andβ(n, Δ) for all values of n, δ_0 and Δ, respectively.     

Homogenization of hyperbolic equations

We consider a self-adjoint matrix elliptic operator A _{ε, ε} > 0, on L ₂(R ^d ;C ⁿ ) given by the differential expression b(D)*g(x/ε)b(D). The matrix-valued function g(x) is bounded, positive definite, and periodic with respect to some lattice; b(D) is an (m × n)-matrix first order differential operator such that m ≥ n and the symbol b(ξ) has maximal rank. We study the operator cosine cos(τA _ε ^1/2 ), where τ ∈ R. It is shown that, as ε → 0, the operator cos(τA _ε ^1/2 ) converges to cos(τ(A ⁰)^1/2) in the norm of operators acting from the Sobolev space H ^s (R ^d ;C ⁿ ) (with a suitable s) to L ₂(R ^d ;C ⁿ ). Here A ₀ is the effective operator with constant coefficients. Sharp-order error estimates are obtained. The question about the sharpness of the result with respect to the type of the operator norm is studied. Similar results are obtained for more general operators. The results are applied to study the behavior of the solution of the Cauchy problem for the hyperbolic equation ? _τ ² u _ε (x, τ) = ?A _ε u _ε (x, τ).     

On Representation of a Solution to the Cauchy Problem by a Fourier Series in Sobolev-Orthogonal Polynomials Generated by Laguerre Polynomials

We consider the problem of representing a solution to the Cauchy problem for an ordinary differential equation as a Fourier series in polynomials l _r,k ^α (x) (k = 0, 1,...) that are Sobolev-orthonormal with respect to the inner product

$$\left\langle {f,g} \right\rangle = \sum\limits_{v = 0}^{r - 1} {{f^{(v)}}(0){g^{(v)}}} (0) + \int\limits_0^\infty {{f^{(r)}}(t)} {g^{(r)}}(t){t^\alpha }{e^{ - t}}dt$$

, and generated by the classical orthogonal Laguerre polynomials L _k ^α (x) (k = 0, 1,...). The polynomials l _r,k ^α (x) are represented as expressions containing the Laguerre polynomials L _n ^α?r (x). An explicit form of the polynomials l _r,k+r ^α (x) is established as an expansion in the powers x ^r+l , l = 0,..., k. These results can be used to study the asymptotic properties of the polynomials l _r,k ^α (x) as k→∞and the approximation properties of the partial sums of Fourier series in these polynomials.

     

Finite configurations in sparse sets

Let E ? ?ⁿ be a closed set of Hausdorff dimension α. For m > n, let{B₁, …, B_k} be n × (m ? n) matrices. We prove that if the system of matrices B_j is non-degenerate in a suitable sense, α is sufficiently close to n, and if E supports a probability measure obeying appropriate dimensionality and Fourier decay conditions, then for a range of m depending on n and k, the set E contains a translate of a non-trivial k-point configuration {B₁y, …, B_ky}. As a consequence, we are able to establish existence of certain geometric configurations in Salem sets (such as parallelograms in ?ⁿ and isosceles right triangles in ?²). This can be viewed as a multidimensional analogue of the result of [25] on 3-term arithmetic progressions in subsets of ?.     

A numerical algorithm for solving a nonstationary problem of optimal control

Let {φ _n ^(α,β) (z)} _n=0 ^∞ be a system of Jacobi polynomials orthonormal on the circle |z| = 1 with respect to the weight (1 ? cos τ)^α+1/2(1 + cos τ)^β+1/2 (α, β > ?1), and let \(\psi _n^{\left( {\alpha ,\beta } \right)*} \left( z \right): = z^n \overline {\psi _n^{\left( {\alpha ,\beta } \right)} \left( {{1 \mathord{\left/ {\vphantom {1 {\bar z}}} \right. \kern-\nulldelimiterspace} {\bar z}}} \right)}\)). We establish relations between the polynomial φ _n ^(α,?1/2) (z) and the nth (C, α ? 1/2)-mean of the Maclaurin series for the function (1 ? z)^?α?3/2 and also between the polynomial φ _n ^(α,?1/2)* (z) and the nth (C, α + 1/2)-mean of the Maclaurin series for the function (1 ? z)^?α?1/2. We use these relations to derive an asymptotic formula for φ _n ^(α,?1/2) (z); the formula is uniform inside the disk |z| < 1. It follows that φ _n ^(α,?1/2) (z) ≠ 0 in the disk |z| ≤ ρ for fixed φ ∈ (0, 1) and α > ?1 if n is sufficiently large.     

Edge-colouring of graphs and hereditary graph properties

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph G, a hereditary graph property P and l ? 1 we define \(X{'_{P,l}}\)(G) to be the minimum number of colours needed to properly colour the edges of G, such that any subgraph of G induced by edges coloured by (at most) l colours is in P. We present a necessary and sufficient condition for the existence of \(X{'_{P,l}}\)(G). We focus on edge-colourings of graphs with respect to the hereditary properties O_k and S_k, where O_k contains all graphs whose components have order at most k+1, and S_k contains all graphs of maximum degree at most k. We determine the value of \(X{'_{{S_k},l}}(G)\) for any graph G, k ? 1, l ? 1, and we present a number of results on \(X{'_{{O_k},l}}(G)\).     

On the approximation of continuous functions of two variables

It is shown that if P _m ^α,β (x) (α, β > ?1, m = 0, 1, 2, …) are the classical Jaboci polynomials, then the system of polynomials of two variables {Ψ _mn ^α,β (x, y)} _m,n=0 ^r = {P _m ^α,β (x)P _n ^α,β (y)} _{m, n=0} ^r (r = m + n ≤ N ? 1) is an orthogonal system on the set Ω _N×N = ?ub;(x _i , y _i ) _i,j=0 ^N , where x _i and y _i are the zeros of the Jacobi polynomial P _n ^α,β (x). Given an arbitrary continuous function f(x, y) on the square [?1, 1]², we construct the discrete partial Fourier-Jacobi sums of the rectangular type S _{m, n, N} ^α,β (f; x, y) by the orthogonal system introduced above. We prove that the order of the Lebesgue constants ∥S _{m, n, N} ^α,β ∥ of the discrete sums S _{m, n, N} ^α,β (f; x, y) for ?1/2 < α, β < 1/2, m + n ≤ N ? 1 is O((mn) ^{q + 1/2}), where q = max?ub;α,β?ub;. As a consequence of this result, several approximate properties of the discrete sums S _{m, n, N} ^α,β (f; x, y) are considered.