Kuratowski's and Wagner's theorems for matroids

In an earlier paper we proved the following theorem, which provides a strengthening of Tutte's well-known characterization of regular (totally unimodular) matroids: A binary matroid is regular if it does not have the Fano matroid or its dual as a series-minor (parallel-minor). In this paper we prove two theorems (Theorems 5.1 and 6.1) which provide the same kind of strengthening for Tutte's characterization of the graphic matroids (i.e., bond-matroids). One interesting aspect of these theorems is the introduction of the matroids of “type R”. It turns out that these matroids are, in at least two different senses, the smallest regular matroids which are neither graphic nor cographic (Theorems 6.2 and 6.3).     

Mersenne's solution for Galileo's problem of the rotating earth

More than twenty years before Huygens and Newton developed formulas for centrifugal acceleration, Mersenne contrived a statisfactory solution for Galileo's problem of the extrusion of bodies from the earth as a result of its daily rotation. Mersenne was able to overcome an error in Galileo's approach without the use either of an explicit notion of infinitesimals or of any clear concept of force. His solution depends on comparing the lengths of two lines, a technique that several historians have claimed to be inadequate for this problem.     

Matrices of 0's and 1's with total support

We determine when there exists a matrix of 0's and 1's with total support (a pattern of a doubly stochastic matrix) having a specified row sum vector and column sum vector.     

On Schmerl's effective version of Brooks' theorem

A new proof is given of Schmerl's recent result that a highly recursive graph G with χ(G) ≤ k according to Brooks' theorem, has a recursive k-colouring.     

On some analogs of Sturm's and Kneser's theorems for nonlinear systems

Analogs of certain conjugate point properties in the calculus of variations are developed for optimal control problems. The main result in this direction is concerned with the characterization of a parameterized family of extremals going through the first backward conjugate point, t_c. A corollary of this result is that for the linear quadratic problem (LQP) there exists at least a one-parameter family of extremals going though the conjugate point which gives the same cost as the candidate extremal, i.e., the extremal control is optimal but nonunique on [t_c, t_f]. An analysis of the effect on the conjugate point of employing penalty functions for terminal equality constraints in the LQP is presented, also. It is shown that the sequence of approximate conjugate points is always conservative, and it converges to the conjugate point of the constrained problem. Furthermore, it is proved that the addition of terminal constraints has the effect of causing the conjugate point to move backward (or remain the same).     

On Axelsson's perturbations

A nice perturbation technique was introduced by Axelsson and further developed by Gustafsson to prove that factorization iterative methods are able, under appropriate conditions, to reach a convergence rate larger by an order of magnitude than that of classical schemes. Gustafsson observed however that the perturbations introduced to prove this result seemed actually unnecessary to reach it in practice. In the present work, on the basis of eigenvalue bounds recently obtained by the author, we offer an alternative approach which brings a partial confirmation of Gustafsson's conjecture.     

Heawood's empire problem

Heawood's map color theorem is generalized to maps of empires on surfaces.     

On Artin's conjecture

Let $\text{F}$ be a family of number fields which are normal and of finite degree over a given number field K. Consider the lattice L(scF) spanned by all the elements of $\text{F}$. The generalized Artin problem is to determine the set of prime ideals of K which do not split completely in any element H of L(scF), H≠K. Assuming the generalized Riemann hypothesis and some mild restrictions on $\text{F}$, we solve this problem by giving an asymptotic formula for the number of such prime ideals below a given norm. The classical Artin conjecture on primitive roots appears as a special case. In another case, if $\text{F}$ is the family of fields obtained by adjoining to $\text{Q}$ the q-division points of an elliptic curve E over $\text{Q}$, the Artin problem determines how often E($\text{F}$_p) is cyclic. If E has complex multiplication, the generalized Riemann hypothesis can be removed by using the analogue of the Bombieri-Vinogradov prime number theorem for number fields.     

Feigin's map revisited

The aim of this note is to understand the injectivity of Feigin's map ${\mathbf{F}}_{\mathbf{w}}$ by representation theory of quivers, where w is the word of a reduced expression of the longest element of a finite Weyl group. This is achieved by the Ringel–Hall algebra approach and a careful studying of a well-known total order on the category of finite-dimensional representations of a valued quiver of finite type. As a byproduct, we also generalize Reineke's construction of monomial bases to non-simply-laced cases.     

Deterministic version of Wigner's semicircle law for the distribution of matrix eigenvalues

It is proved that Wigner's semicircle law for the distribution of eigenvalues of random matrices, which is important in the statistical theory of energy levels of heavy nuclei, possesses the following completely deterministic version. Let A_n=(a_ij), 1?i, ?n, be the nth section of an infinite Hermitian matrix, {λ⁽ⁿ⁾}_1?k?n its eigenvalues, and {u_k⁽ⁿ⁾}_1?k?n the corresponding (orthonormalized column) eigenvectors. Let $\text{v}{}^1{}_{\mathrm{n}}\text{=(a}{}_{\mathrm{n1}}\text{,a}{}_{\mathrm{n2}}\text{,?,a}{}_{\mathrm{n,n?1}}\text{)}$, put

$\text{X}{}_{\mathrm{n}}\text{(t)=[n(n-1)]}{}^{\mathrm{<mtext>-1</mtext><mtext>2</mtext>}}\text{∑}\text{k=1}\text{[(n-1)t]}\text{|v}{}_{\mathrm{n}}{}^1\text{u}{}_{\mathrm{f}}{}^{\mathrm{(n-1)}}\text{|}{}^2\text{,}\text{0?t?1}$

(bookeeping function for the length of the projections of the new row v¹_n of A_n onto the eigenvectors of the preceding matrix A_n?1), and let finally

$\text{F}{}_{\mathrm{n}}\text{(x)=n}{}^{-1}\text{(}\text{number of}\text{λ}{}_{\mathrm{k}}{}^{\mathrm{(n)}}\text{?x}\text{n}\text{,1?k?n)}$

(empirical distribution function of the eigenvalues of $\text{A}{}_{\mathrm{n}}\text{n}$. Suppose (i) $\text{lim}{}_{\mathrm{n}}\text{a}{}_{\mathrm{nn}}\text{n}\text{=0}$, (ii) lim_nX_n(t)=Ct(0<C<∞,0?t?1). Then

$\text{F}{}_{\mathrm{n}}\text{?W(·,C)}\text{(n→∞)}$

,where W is absolutely continuous with (semicircle) density

$\text{w(x,C)=}\text{(2Cπ)}{}^{-1}\text{(4C-x}{}^2{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{for}\text{|x|?2}\text{C}\text{0}\text{for}\text{|x|?2}\text{C}$

     

On Dumont's polynomials

We derive two generating functions and an explicit formula for the polynomials {H_n(x)} studied by Dumont.