Strongly inequivalent representations and Tutte polynomials of matroids

We develop constructive techniques to show that non-isomorphic 3-connected matroids that are representable over a fixed finite field and that have the same Tutte polynomial abound. In particular, for most prime powers q, we construct infinite families of sets of 3-connected matroids for which the matroids in a given set are non-isomorphic, are representable over GF(q), and have the same Tutte polynomial. Furthermore, the cardinalities of the sets of matroids in a given family grow exponentially as a function of rank, and there are many such families.In Memory of Gian-Carlo Rota     

Characterizing Combinatorial Geometries by Numerical Invariants

We show that the projective geometry PG(r − 1,q ) for r & 3 is the only rank- r(combinatorial) geometry with (q^r − 1) / (q − 1) points in which all lines have at least q + 1 points. For r = 3, these numerical invariants do not distinguish between projective planes of the same order, but they do distinguish projective planes from other rank-3 geometries. We give similar characterizations of affine geometries. In the core of the paper, we investigate the extent to which partition lattices and, more generally, Dowling lattices are characterized by similar information about their flats of small rank. We apply our results to characterizations of affine geometries, partition lattices, and Dowling lattices by Tutte polynomials, and to matroid reconstruction. In particular, we show that any matroid with the same Tutte polynomial as a Dowling lattice is a Dowling lattice.     

A condition for the existence of ovals in PG(2, q), q even

A condition is found that determines whether a polynomial over GF(q) gives an oval in PG(2, q), q even. This shows that the set of all ovals of PG(2, q) corresponds to a certain variety of points of PG((q–4)/2, q). The condition improves upon that of Segre and Bartocci, who proved that all the terms of an oval polynomial have even degree. It is suitable for efficient computer searches.     

On the evaluation at (<Emphasis Type="Italic">j</Emphasis>, <Emphasis Type="Italic">j</Emphasis><Superscript>2</Superscript>) of the Tutte polynomial of a ternary matroid

F. Jaeger has shown that up to a ± sign the evaluation at (j, j ²) of the Tutte polynomial of a ternary matroid can be expressed in terms of the dimension of the bicycle space of a representation over GF(3). We give a short algebraic proof of this result, which moreover yields the exact value of ±, a problem left open in Jaeger's paper. It follows that the computation of t(j, j ²) is of polynomial complexity for a ternary matroid.E. Gioan: C.N.R.S., MontpellierM. Las Vergnas: C.N.R.S., Paris     

Combinatorial geometries representable over GF(3) and GF(q). I. The number of points

Letq be a prime power not divisible by 3. We show that the number of points (or rank-1 flats) in a combinatorial geometry (or simple matroid) of rankn representable over GF(3) and GF(q) is at mostn ². Whenq is odd, this bound is sharp and is attained by the Dowling geometries over the cyclic group of order 2.This research was partially supported by National Science Foundation Grant DMS-8521826 and a North Texas State University Faculty Research Grant.     

Combinatorial geometries representable over GF(3) and GF(q). II. Dowling geometries

Letq be an odd prime power not divisible by 3. In Part I of this series, it was shown that the number of points in a rank-n combinatorial geometry (or simple matroid) representable over GF(3) and GF(q) is at mostn ². In this paper, we show that, with the exception ofn = 3, a rank-n geometry that is representable over GF(3) and GF(q) and contains exactlyn ² points is isomorphic to the rank-n Dowling geometry based on the multiplicative group of GF(3).This research was partially supported by the National Science Foundation under Grants DMS-8521826 and DMS-8500494.     

Factorization of the Cyclotomic Polynomialx+ 1 over Finite Fields

The aim of this note is to show that the (well-known) factorization of the 2ⁿ⁺¹th cyclotomic polynomialx2ⁿ+ 1 over GF(q) withq≡ 1 (mod 4) can be used to prove the (more complicated) factorization of this polynomial over GF(q) withq≡ 3 (mod 4).     

Modularity of tangential k-blocks

This paper examines the role of modularity in tangential k-blocks over GF(q). It is shown that if M is a tangential k-block over GF(q) and F is a modular flat of M which is affine over GF(q) then the simple matroid associated with the complete Brown truncation of M by F is also a tangential k-block over GF(q). This enables us to construct tangetial k-blocks over GF(q) of all ranks r where q^k − q + 2⩽r ⩽ q^k. We also consider tangential k-blocks which have modular hyperplanes; bounds are placed on the rank of members of this class and some of their minors are exhibited.     

On Unitals ith Many Baer Sublines

We identify the points of PG(2, q) ith the directions of lines in GF(q ³), viewed as a 3-dimensional affine space over GF(q). Within this frameork we associate to a unital in PG(2, q) a certain polynomial in to variables, and show that the combinatorial properties of the unital force certain restrictions on the coefficients of this polynomial. In particular, if q = p ² where p is prime then e show that a unital is classical if and only if at least (q - 2) secant lines meet it in the points of a Baer subline.     

Descent principle in modular Galois theory

We propound a descent principle by which previously constructed equations over GF(q _n)(X) may be deformed to have incarnations over GF(q)(X) without changing their Galois groups. Currently this is achieved by starting with a vectorial (= additive)q-polynomial ofq-degreem with Galois group GL(m, q) and then, under suitable conditions, enlarging its Galois group to GL(m, q _n) by forming its generalized iterate relative to an auxiliary irreducible polynomial of degreen. Elsewhere this was proved under certain conditions by using the classification of finite simple groups, and under some other conditions by using Kantor’s classification of linear groups containing a Singer cycle. Now under different conditions we prove it by using Cameron-Kantor’s classification of two-transitive linear groups.     

Recipe theorem for the Tutte polynomial for matroids,renormalization group-like approach

Using a quantum field theory renormalization group-like differential equation, we give a new proof of the recipe theorem for the Tutte polynomial for matroids. The solution of such an equation is in fact given by some appropriate characters of the Hopf algebra of isomorphic classes of matroids, characters which are then related to the Tutte polynomial for matroids. This Hopf algebraic approach also allows to prove, in a new way, a matroid Tutte polynomial convolution formula appearing in [W. Kook, V. Reiner, D. Stanton, A convolution formula for the Tutte polynomial, J. Combin. Theory Ser. B 76 (1999) 297–300] and [G. Etienne, M. Las Vergnas, External and internal elements of a matroid basis, Discrete Math. 179 (1998) 111–119].     

Geometry of Cubic and Quartic Hypersurfaces over Finite Fields

Let YPⁿ be a cubic hypersurface defined over GF(q). Here, we study the Finite Field Nullstellensatz of order [q/3] for the set Y(q) of its GF(q)-points, the existence of linear subspaces of PG(n,q) contained in Y(q) and the possibility to join any two points of Y(q) by the union of two lines of PG(n,q) entirely contained in Y(q). We also study the existence of linear subspaces defined over GF(q) for the intersection of Y with s quadrics and for quartic hypersurfaces.     

A note on Tutte polynomials and Orlik–Solomon algebras

Let be a (central) arrangement of hyperplanes in and the dependence matroid of the linear forms . The Orlik–Solomon algebra of a matroid is the exterior algebra on the points modulo the ideal generated by circuit boundaries. The graded algebra is isomorphic to the cohomology algebra of the manifold . The Tutte polynomial is a powerful invariant of the matroid . When is a rank 3 matroid and the θ_Hi are complexifications of real linear forms, we will prove that determines . This result partially solves a conjecture of Falk.     

Tutte polynomials for trees

We define two two-variable polynomials for rooted trees and one two-variable polynomial for unrooted trees, all of which are based on the coranknullity formulation of the Tutte polynomial of a graph or matroid. For the rooted polynomials, we show that the polynomial completely determines the rooted tree, i.e., rooted trees T₁ and T₂ are isomorphic if and only if f(T₁) = f(T₂). The corresponding question is open in the unrooted case, although we can reconstruct the degree sequence, number of subtrees of size k for all k, and the number of paths of length k for all k from the (unrooted) polynomial. The key difference between these three polynomials and the standard Tutte polynomial is the rank function used; we use pruning and branching ranks to define the polynomials. We also give a subtree expansion of the polynomials and a deletion-contraction recursion they satisfy.     

On Invariants and Strict Systems of Irreducible Polynomials Over Henselian Valued Fields

Let g(x) be a monic irreducible defectless polynomial over a henselian valued field (K, v), i.e., K(θ) is a defectless extension of (K, v) for any root θ of g(x). It is known that a complete distinguished chain for θ with respect to (K, v) gives rise to several invariants associated with g(x). Recently Ron Brown studied certain invariants of defectless polynomials by introducing strict systems of polynomial extensions. In this article, the authors establish a one-to-one correspondence between strict systems of polynomial extensions and conjugacy classes of complete distinguished chains. This correspondence leads to a simple interpretation of various results proved for strict systems. The authors give new characterizations of an invariant γ _g introduced by Brown.     

Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids

The chromatic polynomial P_G(q) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals (−∞,0), (0,1) and (1,32/27]. Analogous theorems hold for the flow polynomial of bridgeless graphs and for the characteristic polynomial of loopless matroids. Here we exhibit all these results as special cases of more general theorems on real zero-free regions of the multivariate Tutte polynomial Z_G(q,v). The proofs are quite simple, and employ deletion–contraction together with parallel and series reduction. In particular, they shed light on the origin of the curious number 32/27.     

Latroids and their representation by codes over modules

It has been known for some time that there is a connection between linear codes over fields and matroids represented over fields. In fact a generator matrix for a linear code over a field is also a representation of a matroid over that field. There are intimately related operations of deletion, contraction, minors and duality on both the code and the matroid. The weight enumerator of the code is an evaluation of the Tutte polynomial of the matroid, and a standard identity relating the Tutte polynomials of dual matroids gives rise to a MacWilliams identity relating the weight enumerators of dual codes. More recently, codes over rings and modules have been considered, and MacWilliams type identities have been found in certain cases.

In this paper we consider codes over rings and modules with code duality based on a Morita duality of categories of modules. To these we associate latroids, defined here. We generalize notions of deletion, contraction, minors and duality, on both codes and latroids, and examine all natural relations among these.

We define generating functions associated with codes and latroids, and prove identities relating them, generalizing above-mentioned generating functions and identities.

     

( q,t)-analogues and $GL_{n}({\ma thbb{F}}_{ q})$

We start with a (q,t)-generalization of a binomial coefficient. It can be viewed as a polynomial in t that depends upon an integer q, with combinatorial interpretations when q is a positive integer, and algebraic interpretations when q is the order of a finite field. These (q,t)-binomial coefficients and their interpretations generalize further in two directions, one relating to column-strict tableaux and Macdonald’s “7 ^th variation” of Schur functions, the other relating to permutation statistics and Hilbert series from the invariant theory of GL_n(\mathbbF_q)GL_{n}({\mathbb{F}}_{q}) .     

Splitting Formulas for Tutte Polynomials

We present two splitting formulas for calculating the Tutte polynomial of a matroid. The first one is for a generalized parallel connection across a 3-point line of two matroids and the second one is applicable to a 3-sum of two matroids. An important tool used is the bipointed Tutte polynomial of a matroid, an extension of the pointed Tutte polynomial introduced by Brylawski.     

LU factorizations, q = 0 limits, and p-adic interpretations of some q-hypergeometric orthogonal polynomials

For little q-Jacobi polynomials and q-Hahn polynomials we give particular q-hypergeometric series representations in which the termwise q = 0 limit can be taken. When rewritten in matrix form, these series representations can be viewed as LU factorizations. We develop a general theory of LU factorizations related to complete systems of orthogonal polynomials with discrete orthogonality relations which admit a dual system of orthogonal polynomials. For the q = 0 orthogonal limit functions we discuss interpretations on p-adic spaces. In the little 0-Jacobi case we also discuss product formulas. Dedicated to Dick Askey on the occasion of his seventieth birthday. 2000 Mathematics Subject Classification Primary—33D45, 33D80 Work done at KdV Institute, Amsterdam and supported by NWO, project number 613.006.573.