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.     

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.     

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.     

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.     

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.     

On the combinatorial classification of nondegenerate configurations in the plane

We classify nondegenerate plane configurations by attaching, to each such configuration of n points, a periodic sequence of permutations of {1, 2, …, n} which satisfies some simple conditions; this classification turns out to be appropriate for questions involving convexity. In 1881 Perrin stated that every sequence satisfying these conditions was the image of some plane configuration. We show that this statement is incorrect by exhibiting a counterexample, for n = 5, and prove that for n ? 5 every sequence essentially distinct from this one is realized geometrically by giving a complete classification of configurations in these cases; there is 1 combinatorial equivalence class for n = 3, 2 for n = 4, and 19 for n = 5. We develop some basic notions of the geometry of “allowable sequences” in the course of proving this classification theorem. Finally, we state some results and an open problem on the realizability question in the general case.     

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.     

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.     

Cohomology rings and formality properties of nilpotent groups

We analyze k-stage formality and relate resonance with this type of formality properties. For instance, we show that, for a finitely generated nilpotent group that is k-stage formal, the resonance varieties are trivial up to degree k. We also show that the cohomology ring, truncated up to degree k+1, of a finitely generated nilpotent, k-stage formal group is generated in degree 1; this criterion is necessary and sufficient for a finitely generated, 2-step nilpotent group to be k-stage formal. We compute resonance varieties for Heisenberg-type groups and deduce the degree of partial formality for this class of groups.     

Lattice tensor products. IV

In 1999, for lattices A and B, G. Grätzer and F. Wehrung introduced the lattice tensor product, A?B. In Part I of this paper, we showed that for a finite lattice A and a bounded lattice B, this construction can be "coordinatized,'' that is, represented in B ^A so that the representing elements are easy to recognize. In this note, we show how to extend our method to an arbitrary bounded lattice A to coordinatize A?B.     

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.     

The necklace poset is a symmetric chain order

Let Nn denote the quotient poset of the Boolean lattice, Bn, under the relation equivalence under rotation. Griggs, Killian, and Savage proved that Np is a symmetric chain order for prime p. In this paper, we settle the question posed in that paper, namely whether Nn is a symmetric chain order for all n. This paper provides an algorithm that produces a symmetric chain decomposition (or SCD). We accomplish this by modifying bracketing from Greene and Kleitman. This allows us to take appropriate “middles” of certain chains from the Greene-Kleitman SCD for Bn. We also prove additional properties of the resulting SCD and show that this settles a related conjecture.     

Unicyclic graphs of minimal spectral radius

It was conjectured by Li and Feng in 1979 that the unicyclic graph formed by a cycle of order g linking to an endvertex of a path of length k minimizes the spectral radius of all unicyclic graphs of order g + k and girth g. In 1987, Cao proved that this conjecture is true for k ≥ g(g 2)/8 and false for k = 2 and sufficiently large g. In this note, we show that g 12 suffices for the counterexample and give more counterexamples with large girth for any integer k 1.     

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.     

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.     

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.     

A Brylawski decomposition for finite ordered sets

A decomposition is given for finite ordered sets P and is shown to be a unique decomposition in the sense of Brylawski. Hence there exists a universal invariant g(P) for this decomposition, and we compute g(P) explicitly. Some modifications of this decomposition are considered; in particular, one which forms a bidecomposition together with disjoint union.     

Shift-invariant spaces on LCA groups

In this article we extend the theory of shift-invariant spaces to the context of LCA groups. We introduce the notion of H-invariant space for a countable discrete subgroup H of an LCA group G, and show that the concept of range function and the techniques of fiberization are valid in this context. As a consequence of this generalization we prove characterizations of frames and Riesz bases of these spaces extending previous results, that were known for Rd and the lattice Zd.     

On t-branch split cuts for mixed-integer programs

In this paper we study the t-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). They presented a family of mixed-integer programs with n integer variables and a single continuous variable and conjectured that the convex hull of integer solutions for any n has unbounded rank with respect to (n?1)-branch split cuts. It was shown earlier by Cook et al. (Math Program 47:155–174, 1990) that this conjecture is true when n = 2, and Li and Richard proved the conjecture when n = 3. In this paper we show that this conjecture is also true for all n > 3.     

On a problem ofn (2)-permutable semigroups

In this paper we give, for a special class of semigroups, a necessary and sufficient condition under which a semigroup is (m,n)-commutative for some positive integersm andn. With the aid of this result we give a partial answer to the following problem raised in [3]: Does then ₍₂₎-permutability (n≥4) of a semigroupS imply the (t,r)-commutativity ofS for somet,r? We show that every finiten ₍₂₎-permutable semigroup is (t,r)-commutative for somet andr.