Complementary bases of a matroid

Let e₁, e′₁, e₂, e′₂, …, e_n, e′_n be the elements of matroid M. Suppose that {e₁, e₂, …;, e_n} is a base of M and that every circuit of M contains at least m + 1 elements. We prove that there exist at least 2^m bases, called complementary bases, of M with the property that only one of each complementary pair e_j, e′_j is contained in any base.We also prove an analogous result for the case where E is partitioned into E₁, E₂, …, E_n and the initial base contains |E_j| ? 1 elements from partition E_j.     

Distance-restricted matching extension in planar triangulations

A graph G is said to have property E(m,n) if it contains a perfect matching and for every pair of disjoint matchings M and N in G with |M|=m and |N|=n, there is a perfect matching F in G such that M⊆F and N∩F=0?. In a previous paper (Aldred and Plummer 2001) [2], an investigation of the property E(m,n) was begun for graphs embedded in the plane. In particular, although no planar graph is E(3,0), it was proved there that if the distance among the three edges is at least two, then they can always be extended to a perfect matching. In the present paper, we extend these results by considering the properties E(m,n) for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension.     

Restricted matching in graphs of small genus

A graph G with at least 2n+2 vertices is said to be n-extendable if every set of n disjoint edges in G extends to (i.e., is a subset of) a perfect matching. More generally, a graph is said to have property E(m,n) if, for every matching M of size m and every matching N of size n in G such that M∩N=0?, there is a perfect matching F in G such that M⊆F, but F∩N=0?. G is said to have property E(0,0) if it has a perfect matching. The study of the properties E(m,n) is referred to as the study of restricted matching extension.In [M. Porteous, R. Aldred, Matching extensions with prescribed and forbidden edges, Australas. J. Combin. 13 (1996) 163-174; M. Porteous, Generalizing matching extensions, M.A. Thesis, University of Otago, 1995; A. McGregor-Macdonald, The E(m,n) property, M.Sc. Thesis, University of Otago, 2000], Porteous and Aldred, Porteous and McGregor-Macdonald, respectively, studied the possible implications among the properties E(m,n) for various values of m and n. In an earlier paper [R.E.L. Aldred, Michael D. Plummer, On restricted matching extension in planar graphs, in: 17th British Combinatorial Conference (Canterbury 1999), Discrete Math. 231 (2001) 73-79], the present authors completely determined which of the various properties E(m,n) always hold, sometimes hold and never hold for graphs embedded in the plane. In the present paper, we do the same for embeddings in the projective plane, the torus and the Klein bottle.     

A threshold property for intersections in a finite set

Let F be any family of subsets of a finite set E and let n be an integer, n<|F|. Under what condition does the knowledge of cardinals of m-intersections in F, for all m≤n, univocally determine the cardinal of any intersection in F, and what is the minimal condition? We give a complete answer to that. For any n, this determination property is satisfied by n if and only if |E|<2ⁿ, without further condition on F.     

Une relation de séparation entre cocircuits d'un matroide

Let S₁′S₂′S₃′ be 3 distinct cocircuits of a matroid M on a set E. We say that S₁′ does not separate S₂′ and S₃′ when S₂′\S₁′ and S₃′\S₁′ are included in one single and the same component of the submatroid M × (E\S₁′). Our main result is: A matroid is graphic if and only if from any 3 cocircuits having a non-empty intersection there is at least one which separates the two others.     

Collinear subsets of lattice point sequences—An analog of Szemerédi's theorem

Szemerédi's theorem states that given any positive number B and natural number k, there is a number n(k, B) such that if n ? n(k, B) and 0 < a₁ < … < a_n is a sequence of integers with a_n ? Bn, then some k of the a_i form an arithmetic progression. We prove that given any B and k, there is a number m(k, B) such that if m ? m(k, B) and u₀, u₁, …, u_m is a sequence of plane lattice points with ∑_i=1^m…u_i ? u_i?1… ? Bm, then some k of the u_i are collinear. Our result, while similar to Szemerédi's theorem, does not appear to imply it, nor does Szemerédi's theorem appear to imply our result.     

Milnor K-Groups and Finite Field Extensions

Let E/F be a finite separable field extension and let m denote the integral part of log₂ [E : F]. David Leep recently showed that if char(F) 2, then for n m the nth power of the fundamental ideal in the Witt ring of E satisfies the equality I ⁿ E = I ^n–m F · I ^m E. The aim of this note is to prove the analogous equality for the Milnor K-groups, that is K _n E = K _n–m F · K _m E for n m. In either of these equalities one may not replace m by m – 1, as examples of certain m-quadratic extensions indicate.     

Matrices of zeros and ones with fixed row and column sum vectors

Let m and n be positive integers, and let R=(r₁,…,r_m) and S=(s₁,…,s_n) be nonnegative integral vectors. We survey the combinational properties of the set of all m × n matrices of 0's and 1's having r_i1's in row i ands_i 1's in column j. A number of new results are proved. The results can be also be formulated in terms of a set of bipartite graps with bipartition into m and n vertices having degree sequence R and S, respectively. They can also be formulated in terms of the set of hypergraphs with m vertices having degree sequence R and n edges whose cardinalities are given by S.     

Roth's theorems and decomposition of modules

It is shown that there is a connection between Roth's theorems on similarity and equivalence of block-triangular matrices and decomposition of modules. The module property is that if $\text{M?}\text{N⊕M}\text{N}$, then N is a summand of M. This holds for any commutative ring if M is finitely presented. New proofs of Roth's theorems are given for commutative rings. Some results are established in the noncommutative case.     

Linear preservers of row-dense matrices

Let M_m,n be the set of all m × n real matrices. A matrix A ∈ M_m,n is said to be row-dense if there are no zeros between two nonzero entries for every row of this matrix. We find the structure of linear functions T: M_m,n → M_m,n that preserve or strongly preserve row-dense matrices, i.e., T(A) is row-dense whenever A is row-dense or T(A) is row-dense if and only if A is row-dense, respectively. Similarly, a matrix A ∈ M_n,m is called a column-dense matrix if every column of A is a column-dense vector. At the end, the structure of linear preservers (strong linear preservers) of column-dense matrices is found.     

Subspaces of matrices with special rank properties

Let K be a field and let M_m×n(K) denote the space of m×n matrices over K. We investigate properties of a subspace M of M_m×n(K) of dimension n(m-r+1) in which each non-zero element of M has rank at least r and enumerate the number of elements of a given rank in M when K is finite. We also provide an upper bound for the dimension of a constant rank r subspace of M_m×n(K) when K is finite and give non-trivial examples to show that our bound is optimal in some cases. We include a similar a bound for the maximum dimension of a constant rank subspace of skew-symmetric matrices over a finite field.     

Comparing Zagreb indices for connected graphs

It was conjectured that for each simple graph G=(V,E) with n=|V(G)| vertices and m=|E(G)| edges, it holds M₂(G)/m≥M₁(G)/n, where M₁ and M₂ are the first and second Zagreb indices. Hansen and Vuki?evi? proved that it is true for all chemical graphs and does not hold in general. Also the conjecture was proved for all trees, unicyclic graphs, and all bicyclic graphs except one class. In this paper, we show that for every positive integer k, there exists a connected graph such that m−n=k and the conjecture does not hold. Moreover, by introducing some transformations, we show that M₂/(m−1)>M₁/n for all bicyclic graphs and it does not hold for general graphs. Using these transformations we give new and shorter proofs of some known results.     

New polytopes from products

We construct a new 2-parameter family Emn, m,n?3, of self-dual 2-simple and 2-simplicial 4-polytopes, with flexible geometric realisations. E₄₄ is the 24-cell. For large m,n the f-vectors have “fatness” close to 6. The Et-construction of Paffenholz and Ziegler applied to products of polygons yields cellular spheres with the combinatorial structure of Emn. Here we prove polytopality of these spheres. More generally, we construct polytopal realisations for spheres obtained from the Et-construction applied to products of polytopes in any dimension d?3, if these polytopes satisfy some consistency conditions. We show that the projective realisation space of E₃₃ is at least nine-dimensional and that of E₄₄ at least four-dimensional. This proves that the 24-cell is not projectively unique. All Emn for relatively prime m,n?5 have automorphisms of their face lattice not induced by an affine transformation of any geometric realisation. The group Zm×Zn generated by rotations in the two polygons is a subgroup of the automorphisms of the face lattice of Emn. However, there are only five pairs (m,n) for which this subgroup is geometrically realisable.     

Martingales in Banach Lattices

In this article, we present a version of martingale theory in terms of Banach lattices. A sequence of contractive positive projections (E_n) on a Banach lattice F is said to be a filtration if E_nE_m = E_{n∧ m}. A sequence (x_n) in F is a martingale if E_nx_m = x_n whenever n ≤ m. Denote by M = M(F, (E_n)) the Banach space of all norm uniformly bounded martingales. It is shown that if F doesn’t contain a copy of c₀ or if every E_n is of finite rank then M is itself a Banach lattice. Convergence of martingales is investigated and a generalization of Doob Convergence Theorem is established. It is proved that under certain conditions one has isometric embeddings . Finally, it is shown that every martingale difference sequence is a monotone basic sequence. Mathematics Subject Classification (2000). 60G48, 46B42     

Functions on tableau frames

In a previous paper the authors used an algorithm for a bijection from the set F of all functions with nonnegative integral values defined on a Young tableau frame Φ onto the set E of all reverse plane partitions (rpp) on Φ in their new proof of R.P. Stanley's generating function for rpp. The algorithm gave new and clear combinatorial significance to the hook numbers of Φ as lengths of zigzag paths but left open the question of invariance of the bijection under interchange of the roles of rows and columns.Here this invariance is proved and the bijection is generalized to allow the entries to be in any linearly ordered additive group. The new algorithms involve n-tuples of paths and use the discreteness of the frame to introduce quantum falls or rises in the entries. New light is shed by considering a tableau frame to be a union of certain rectangles and the hook number of a node to be the number of these rectangles containing the node.     

On a finite rational criterion for the irreducibility of a matrix

A matrix A ∈ M _n (C) is said to be irreducible if the only orthoprojectors that commute with A are the zero and unit matrices. A finite rational criterion for irreducibility is proposed. The criteria for verification of this property that can be found in the literature are neither finite nor rational.     

Parabolic maximal functions and potentials of distributions in Hp

A linear homogeneous ODE is constructed, among whose solutions are all products of solutions of two given linear homogeneous ODE's L_m[u]=0, M_n[v]=0, in some classes. Its order is the minimum and its coefficients can be obtained by a finite number of rational operations and differentiations on the coefficients of L_m, M_n. The problem is considered (locally) both in the real and in the complex domain, around an isolated singularity. Examples are also given.     

On graphsG for which all large trees areG-good

LetG be a graph satisfying x(G) = k. The following problem is considered: WhichG have the property that, if n is large enough, the Ramsey numberr(G, T) has the value (k — 1)(n — 1) + 1 for all treesT onn vertices? It is shown thatG has this property if and only if for somem, G is a subgraph of bothL _k,m andM _K.m , whereL _k,m andM _k,m are two particulark-chromatic graphs. Indeed, it is shown thatr(L _k,m ,M _k,m ,T _n ) = (k — 1)(n — 1) + 1 whenn is large.     

Mean matrices and infinite divisibility

We consider matrices M with entries m_ij = m(λ_i, λ_j) where λ₁, … ,λ_n are positive numbers and m is a binary mean dominated by the geometric mean, and matrices W with entries w_ij = 1/m (λ_i, λ_j) where m is a binary mean that dominates the geometric mean. We show that these matrices are infinitely divisible for several much-studied classes of means.