The proof on the conjecture of extremal graphs for the kth eigenvalues of trees

We consider the only remaining unsolved case n≡0 (mod k) for the largest kth eigenvalue λ_k.of trees with n vertices. In this paper, the conjecture for this problem in [Shao Jia-yu, On the largest kth eignevalues of trees, Linear Algebra Appl. 221 (1995) 131] is proved and (from this) the complete solution to this problem, the best upper bound and the extremal trees of λ_k, is given in general cases above.     

An interrelation between line graphs,eigenvalues, and matroids

If L(G) is the line graph of G, and A(L(G)), the adjacency matrix of L(G), acts on a vector x, this vector may be thought of as an integral chain of G. The eigenspace of L(G) determines a matroid for G. For the eigenvalue ?2, this matroid has a geometric interpretation, and from this we obtain all eigenvectors corresponding to this eigenvalue. Matroids are normally considered over integral domains, and the results for eigenvectors are generalized to a geometric interpretation for all integral domains. These results are applied to the ring of complex numbers, and strict bounds for the least eigenvalue of a line graph are obtained.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

On the generalized Burgers equation

The present paper is concerned with the initial boundary value problem for the generalized Burgers equation u _t + g(t, u)u _x + f(t, u) = εu _xx which arises in many applications. We formulate a condition guaranteeing the a priori estimate of max |u _x | independent of ε and t and give an example demonstrating the optimality of this condition. Based on this estimate we prove the global existence of a unique classical solution of the problem and investigate the behavior of this solution for ε → 0 and t → + ∞. The Cauchy problem for this equation is considered as well.     

A characterization of powerful p-groups

In [10] Benjamin Klopsch and Ilir Snopce recently posted the conjecture that for p ≥ 3 and G a torsion-free pro-p group, d(G) = dim(G) is a sufficient and necessary condition for the pro-p group G to be uniform. They pointed out that this follows from the more general question of whether for a finite p-group d(G) = log _p (|Ω₁(G)|) is a sufficient and necessary condition for the group G to be powerful. In this short note we will give a positive answer to this question for p ≥ 5.     

On the distribution of the ratio of the largest eigenvalue to the trace of a Wishart matrix

The ratio of the largest eigenvalue divided by the trace of a p×p random Wishart matrix with n degrees of freedom and an identity covariance matrix plays an important role in various hypothesis testing problems, both in statistics and in signal processing. In this paper we derive an approximate explicit expression for the distribution of this ratio, by considering the joint limit as both p,n→∞ with p/n→c. Our analysis reveals that even though asymptotically in this limit the ratio follows a Tracy-Widom (TW) distribution, one of the leading error terms depends on the second derivative of the TW distribution, and is non-negligible for practical values of p, in particular for determining tail probabilities. We thus propose to explicitly include this term in the approximate distribution for the ratio. We illustrate empirically using simulations that adding this term to the TW distribution yields a quite accurate expression to the empirical distribution of the ratio, even for small values of p,n.     

Approximating earliest arrival flows with flow-dependent transit times

For the earliest arrival flow problem one is given a network G=(V,A) with capacities u(a) and transit times τ(a) on its arcs a∈A, together with a source and a sink vertex s,t∈V. The objective is to send flow from s to t that moves through the network over time, such that for each time θ∈[0,T) the maximum possible amount of flow up to this time reaches t. If, for each θ∈[0,T), this flow is a maximum flow for time horizon θ, then it is called earliest arrival flow. In practical applications a higher congestion of an arc in the network often implies a considerable increase in transit time. Therefore, in this paper we study the earliest arrival problem for the case that the transit time of each arc in the network at each time θ depends on the flow on this particular arc at that time θ.For constant transit times it has been shown by Gale that earliest arrival flows exist for any network. We give examples, showing that this is no longer true for flow-dependent transit times. For that reason we define a relaxed version of this problem where the objective is to find flows that are almost earliest arrival flows. In particular, we are interested in flows that, for each θ∈[0,T), need only α-times longer to send the maximum flow to the sink. We give both constant lower and upper bounds on α; furthermore, we present a constant factor approximation algorithm for this problem.     

Two-point Taylor expansions in the asymptotic approximation of double integrals. Application to the second and fourth Appell functions

The main difficulty in Laplace's method of asymptotic expansions of double integrals is originated by a change of variables. We consider a double integral representation of the second Appell function F₂(a,b,b^′,c,c^′;x,y) and illustrate, over this example, a variant of Laplace's method which avoids that change of variables and simplifies the computations. Essentially, the method only requires a Taylor expansion of the integrand at the critical point of the phase function. We obtain in this way an asymptotic expansion of F₂(a,b,b^′,c,c^′;x,y) for large b, b^′, c and c^′. We also consider a double integral representation of the fourth Appell function F₄(a,b,c,d;x,y). We show, in this example, that this variant of Laplace's method is uniform when two or more critical points coalesce or a critical point approaches the boundary of the integration domain. We obtain in this way an asymptotic approximation of F₄(a,b,c,d;x,y) for large values of a,b,c and d. In this second example, the method requires a Taylor expansion of the integrand at two points simultaneously. For this purpose, we also investigate in this paper Taylor expansions of two-variable analytic functions with respect to two points, giving Cauchy-type formulas for the coefficients of the expansion and details about the regions of convergence.     

An implicit-function theorem for inclusions

We consider the question of the solvability of an inclusion F(x, σ) ∈ A, i.e., of determining a mapping (implicit function) σ ? x(σ) defined on a set such that F(x(σ), σ) ∈ A for any σ from this set. Results of this kind play a key role in the different branches of analysis and, especially, in the theory of extremal problems, where they are the main tool for deriving conditions for an extremum.     

Equidistribution of signs for modular eigenforms of half integral weight

Let f be a cusp form of weight k + 1/2 and at most quadratic nebentype character whose Fourier coefficients a(n) are all real. We study an equidistribution conjecture of Bruinier and Kohnen for the signs of a(n). We prove this conjecture for certain subfamilies of coefficients that are accessible via the Shimura lift by using the Sato–Tate equidistribution theorem for integral weight modular forms. Firstly, an unconditional proof is given for the family {a(tp ²)} _p , where t is a squarefree number and p runs through the primes. In this case, the result is in terms of natural density. To prove it for the family {a(tn ²)} _n where t is a squarefree number and n runs through all natural numbers, we assume the existence of a suitable error term for the convergence of the Sato–Tate distribution, which is weaker than one conjectured by Akiyama and Tanigawa. In this case, the results are in terms of Dedekind–Dirichlet density.     

Lower Bounds for Scheduling on Identical Parallel Machines with Heads and Tails

In this paper, we investigate new lower bounds for the P|r _j ,q _j |C _max scheduling problem. A new bin packing based lower bound, as well as several new lifting procedures are derived for this strongly NP -hard problem. Extensive numerical experiments show that the proposed lower bounds consistently outperform the best existing ones.     

Riemann Boundary Value Problems for Triharmonic Functions in Clifford Analysis

In this paper, we study the R _m (m > 0) Riemann boundary value problem for triharmonic functions with values in a universal Clifford algebra Cl(V _n,n ). By using the Plemelj formula and generalized Liouville theorem for triharmonic functions, the explicit representation of solution of this problem is given.     

A note on Vizing's independence number conjecture of edge chromatic critical graphs

In 1968, Vizing conjectured that, if G is a Δ-critical graph with n vertices, then α(G)?n/2, where α(G) is the independence number of G. In this note, we verify this conjecture for n?2Δ.     

A family of orthonormal wavelet bases with dilation factor 4

In this paper, we study a method for the construction of orthonormal wavelet bases with dilation factor 4. More precisely, for any integer M>0, we construct an orthonormal scaling filter mM(ξ) that generates a mother scaling function ?M, associated with the dilation factor 4. The computation of the different coefficients of ²|mM(ξ)| is done by the use of a simple iterative method. Also, this work shows how this construction method provides us with a whole family of compactly supported orthonormal wavelet bases with arbitrary high regularity. A first estimate of α(M), the asymptotic regularity of ?M is given by α(M)∼0.25M. Examples are provided to illustrate the results of this work.     

On defining numbers of circular complete graphs

Let d(σ) stand for the defining number of the colouring σ. In this paper we consider and for the onto χ-colourings γ of the circular complete graph K_n,d. In this regard we obtain a lower bound for d^min(K_n,d) and we also prove that this parameter is asymptotically equal to χ-1. Also, we show that when χ?4 and s≠0 then d^max(K_χd-s,d)=χ+2s-3, and, moreover, we prove an inequality relating this parameter to the circular chromatic number for any graph G.     

The convergence behavior of q-continued fractions on the unit circle

In a previous paper, we showed the existence of an uncountable set of points on the unit circle at which the Rogers-Ramanujan continued fraction does not converge to a finite value. In this present paper, we generalise this result to a wider class of q-continued fractions, a class which includes the Rogers-Ramanujan continued fraction and the three Ramanujan-Selberg continued fractions. We show, for each q-continued fraction, G(q), in this class, that there is an uncountable set of points, Y _G , on the unit circle such that if y ? Y _G then G(y) does not converge to a finite value. We discuss the implications of our theorems for the convergence of other q-continued fractions, for example the Göllnitz-Gordon continued fraction, on the unit circle.     

TRANSPORTATION INEQUALITIES FOR WEAKLY DEPENDENT SEQUENCES

In [3], they gave necessary and sufficient condition for T 1 C and then as applications T 1 C for weakly dependent sequences was established. In this note, based on Gozlan-L′eonard characterization for W 1 H -inequalities, we extends this result to W 1 H inequalities.     

Rings of continuous functions on σ-frames

This paper deals with the ?-rings RS of all real-valued continuous functions on a completely regular σ-frame. It shows that, in marked contrast with the situation for frames, any ?-ring homomorphism RS→RT results from a σ-frame homomorphism S→T. Further, it proves the analogue of this for integer-valued continuous functions and 0-dimensional σ-frames. In all, this demonstrates that the important classical difference between Alexandroff spaces and Tychonoff spaces with respect to the real-valued continuous functions carries over fully to the pointfree setting - indeed, it adds the integer-valued case which seems to be new in this context.     

A polynomial-time algorithm for finding zero-sums

Erdös, Ginzburg and Ziv proved that any sequence of 2n−1 (not necessary distinct) members of the cyclic group Z_n contains a subsequence of length n the sum of whose elements is congruent to zero modulo n. There are several proofs of this celebrated theorem which combine combinatorial and algebraic ideas. Our main result is an alternative and constructive proof of this result. From this proof, we deduce a polynomial-time algorithm for finding a zero-sum n-sequence of the given (2n−1)-sequence of an abelian group G with n elements (a fortiori for Z_n). To the best of our knowledge, this is the first efficient algorithm for finding zero-sum n-sequences.     

The asymptotic distribution of a goodness of fit statistic for factorial invariance

Suppose that random factor models with k factors are assumed to hold for m, p-variate populations. A model for factorial invariance has been proposed wherein the covariance or correlation matrices can be written as Σ_i = LC_iL′ + σ_i²I, where C_i is the covariance matrix of factor variables and L is a common factor loading matrix, i = 1,…, m. Also a goodness of fit statistic has been proposed for this model. The asymptotic distribution of this statistic is shown to be that of a quadratic form in normal variables. An approximation to this distribution is given and thus a test for goodness of fit is derived. The problem of dimension is considered and a numerical example is given to illustrate the results.