A matroid / geometry problem and conjecture

Rather than let this blog die off due to lack of posts, I thought I’d write about a small but annoying problem that I’ve been thinking about recently, but without success, and a natural conjecture that has arisen from it.

[Note: On some browsers there appears to be a sizing problem with the images WordPress uses for LaTeX formulas, and they appear ten times the right size. If this happens, reloading the webpage seems to fix it]

The problem arose in the context of binary matroids, but because a binary matroid is really just a set of points in a binary vector space, it can be phrased entirely as a linear algebra problem.

So let {M} be a set of non-zero vectors in the vector space {V = GF(2)^r} such that {M} spans {V} and, for reasons to be clarified later, no vector in {M} is independent of the others. In matroid terminology, this just says that {M} is a simple binary matroid of rank {r} with no coloops.

Then define a  basis of {M} to be a linearly independent subset of {M} of rank {r} (in other words, just a basis of {V} and a circuit of {M} to be a minimally dependent set of vectors, i.e. a set of vectors that is linearly dependent but any proper subset of which is linearly independent.

As an example, take {M = PG(2,2)} (a.k.a the Fano plane) — this means to take all the non-zero vectors in {GF(2)^3}. This has 28 bases (7 choices for a first vector {v}, 6 for a second vector {w} and then 4 for the third vector which cannot be {v}, {w} or {v+w} , then all divided by 6 because this counts each basis {6} times). It has 7 circuits of size 3 (each being of the form {v}, {w}, {v+w}) and 7 circuits of size 4, being the complements of the circuits of size 3, for a total of 14 circuits.

Letting {b(M)}, {c(M)} denote the numbers of bases and circuits of {M} respectively, the question is about the ratio of these two numbers. More precisely,

Determine a lower bound, in terms of the rank {r}, for the ratio {\frac{b(M)}{c(M)}}?

Continue reading “A matroid / geometry problem and conjecture”

The collinearity graph of a polar space

A partial linear space of order (s,t) is a geometry of points and lines such that every pair of distinct points lie on at most one line, there are s+1 points on every line, and there are t+1 lines through any point. We also require a non-degeneracy condition such as we don’t have all the points incident with just one line, and s,t>1. Now an antiflag is a point P and line \ell that are not incident, and the antiflag numbers for a partial linear space are the possible values for the number of lines on P that are concurrent with \ell. For example, a projective plane of order q is a partial linear space of order (q,q) with single antiflag number q+1. A generalised quadrangle has just one antiflag number, and it is 1, whereas a polar space of rank at least 3 has antiflag numbers 1 and s+1.

Now if there is a single antiflag number \alpha, then the partial linear space is said to be a partial geometry. The collinearity graph of a partial geometry is the undirected graph whose vertices are the points, and they are adjacent if they are collinear. It is not difficult to prove that the collinearity graph of any partial geometry is strongly regular; that is, it is a regular graph and there are two constants \lambda and \mu such that for any pair of adjacent (resp. non-adjacent) vertices, there are \lambda (resp. \mu) common neighbours.

The antiflag condition “1 or s+1” is the defining axiom of a polar space, and this is a highly nontrivial result of Buekenhout and Shult (1974). Moreover, we know that a polar space of rank at least 3 is “classical” by a theorem of F. D. Veldkamp and J. Tits, and so the collinearity graph of such a partial linear space must have a rank 3 automorphism group. It then follows that the collinearity graph of a polar space is strongly regular; the rank 2 case is simpler as then we have generalised quadrangles and they are partial geometries.

So we know that the collinearity graphs of polar spaces are strongly regular, but is there a simpler proof of this fact?

Continue reading “The collinearity graph of a polar space”

The Merino-Welsh Conjecture

The Merino-Welsh conjecture is an intriguing conjecture relating three graphical parameters, namely the numbers of spanning trees, acyclic orientations and totally cyclic orientations of a graph.

First recall the definitions of these terms: an orientation of a graph is an assignment of directions to the edges of the graph (thus there are 2^m orientations for an m-edge graph), and an orientation is called acyclic if the resulting directed graph contains no directed cycle and, at the opposite extreme, totally cyclic if every directed edge is contained in a directed cycle. A spanning tree is a connected  subgraph containing every vertex of the graph, but containing no cycles; it is easy to see that a spanning tree of an n-vertex graph has (n-1) edges. We denote these three quantities \tau(G) for trees, \alpha(G) for acyclic orientations and \alpha^*(G) for totally cyclic orientations.  Then we have the conjecture, due to serial conjecturer Dominic Welsh, and his former student Criel Merino.

Conjecture (Merino, Welsh) If G is a multigraph with no bridges or loops, then \tau(G) \le \max(\alpha(G),\alpha^*(G)).

There are various stronger versions of this conjecture, such as having \tau(G) less than the arithmetic or geometric mean of the other two parameters, but all seem equally difficult and equally unsolved.

Speaking very loosely, if the graph is somewhat sparse, with relatively few edges given the number of vertices, then acyclic orientations are favoured and so \alpha(G) tends to dominate the number of spanning trees, while if the graph is dense, then the number of totally cyclic orientations tends to dominate. The best partial results on the conjecture are essentially about graphs at one end of the spectrum or the other, where one or other of the parameters dominates so much that relatively coarse, though ingenious, approximations are sufficient to demonstrate this fact. So, the following results are known, due to Carsten Thomassen:

  • If the bridgeless multigraph G has at least 4n-4 edges, then \tau(G) < \alpha^*(G).
  • If G is a graph (not multigraph) with at most 16n/15 edges, then \tau(G) < \alpha(G).

Obviously there is a huge gap between these bounds. It is conceivable however that there is a range of low densities where \alpha(G) dominates \tau (i.e. regardless of the structure of G) and a range of higher densities where \alpha^*(G) dominates \tau, and that these two ranges overlap. In fact, Thomassen asked whether m = 2n-2 edges could possibly be the dividing point, so that any multigraph with at most 2n-2 edges has \alpha(G) < \tau(G) and any multigraph with at least 2n-2 edges has \tau(G) < \alpha^*(G). Unfortunately this is not true, as there are graphs with exactly 2n-2 edges that have more spanning trees than acyclic orientations.

In some sense, although it may work, this approach seems rather unsatisfactory — the conjecture concerns the interplay of two dual parameters whereas the known results essentially focus on just one of the two.  This follows because all three parameters are actually evaluations of the Tutte polynomial of the graph at various points. In fact, if T is the Tutte polynomial of G, then:

  • \tau(G) = T(1,1)
  • \alpha(G) = T(2,0)
  • \alpha^*(G) = T(0,2)

So if G is planar, then it has the same number of spanning trees as its planar dual, but the numbers of acyclic and totally cyclic orientations swap round. Of course, we don’t need to restrict ourselves to planar graphs – the Tutte polynomial is defined for any matroid, graphic or otherwise, and so the conjecture can be made just as T(1,1) \le \max(T(2,0),T(0,2)) without any reference to the interpretations of these evaluations.  So really, rather than crude approximations based on edge or element densities, it would be much more satisfying if there were some structural reason for the truth of the conjecture that exploited this duality – perhaps some way of defining a map from spanning trees to orientations that could be massaged into a suitable injective map.

As well as evaluating the Tutte polynomial at specific points to get numbers, we can get a variety of 1-variable polynomials from it by partially specifying the values, and lots of common graph and matroid polynomials (chromatic, flow, reliability etc) arise in this way. So we could define f(z) = T(1+z,1-z) and consider the behaviour of this single-variable polynomial for z \in [-1,1]. In particular, it is quite possible that f(z) is convex throughout its domain, except for the case where G is a tree with every edge doubled, in which case f(z) is actually constant. Conde and Merino said that this would make a “rather more daring strengthening of the conjecture” which I have paraphrased to incorporate matroids:

Conjecture (Conde-Merino, but for graphs only)  If M is a matroid with no loops or co-loops with Tutte polynomial T, then T(1-z,1+z) is convex on the range z \in [-1,1] unless M is a direct sum of pairs of parallel elements.

Two problems on Hamilton cycles

Michael’s last post on cubic vertex-transitive graphs mentioned, almost in passing, that every graph in the new catalogue has been checked to see whether it contains a Hamilton cycle – in other words, a cycle passing through each vertex exactly once.

The reason to check this particular property is a very famous and very perplexing conjecture:

Conjecture: Every connected vertex-transitive graph, other than K_2, the Petersen graph P, the Coxeter graph C and the two graphs obtained from P and C by replacing each vertex with a triangle, has a Hamilton cycle.

Naturally enough, the five graphs in the statement are the only vertex-transitive graphs that are known to not have Hamilton cycles. Of these, K_2 can be viewed as a triviality and ignored, but none of the others are Cayley graphs. So a related conjecture is often expressed as follows:

Conjecture: Every connected Cayley graph has a Hamilton cycle.

I don’t know who actually first stated these as conjectures – certainly Lovász made a much weaker conjecture about transitive graphs having Hamilton paths, but I’m not sure whether he made these stronger conjectures.

Continue reading “Two problems on Hamilton cycles”

Chromatic Roots – the multiplicity of 2?

My favourite problems in the theory of chromatic roots have a tendency to crop up frequently and I often find myself frantically searching through old emails or (worse) trying to dig up old notes.

One of these problems is the following question:

Is there a combinatorial interpretation for the multiplicity of 2 as a root of the chromatic polynomial of a graph?

(For general background, see my previous post on chromatic roots and the accompanying PDF.)

The specific background to this question is that there are well-understood combinatorial interpretations for the multiplicity of 0 as a chromatic root — it is simply the number of connected components of the graph. If a graph is connected (and hence 0 is a simple chromatic root), then the multiplicity of 1 as a chromatic root is the number of blocks (maximal 2-connected components) of the graph.  So we would like a statement that says “if a graph is 2-connected (and so both 0 and 1 are simple chromatic roots) then the multiplicity of 2 as a chromatic root is the number of ….”. Unfortunately it all grinds to a halt here because,  to my knowledge,  nobody knows how to complete that sentence.

Continue reading “Chromatic Roots – the multiplicity of 2?”

Chromatic Roots I

On Friday, I gave a talk (chromaticpolynomials) to the “Junior Mathematics Seminar” in our department; this is a seminar attended and organized by the students, with staff only allowed as speakers.

I chose to speak about one of my favourite topics, namely the chromatic roots of graphs, for three reasons: firstly, it is a very accessible topic for undergraduates, secondly, I have spoken about it frequently and so have many diagrams and plots already prepared, and thirdly, because Alan Sokal and I (along with other collaborators) are having another push at trying to make some progress with some of the outstanding conjectures.

One of the questions is how to tighten the bounds on chromatic roots as a function of the maximum degree \Delta(G) of a graph G. It had long been conjectured, by Norman Biggs and his collaborators, that chromatic roots of graphs should be bounded by some function f(\Delta(G)) of the maximum degree. This was eventually proved by Alan (http://arxiv.org/abs/cond-mat/9904146) but the bound he proved — that chromatic roots have modulus no more than about 8\Delta(G) — is almost certainly nowhere near tight.

I have a very strong conjecture on which I have made no progress in 20 years — my early computations on chromatic roots made me believe the following.

Conjecture: The chromatic root of largest modulus among all r-regular graphs is a chromatic root of the complete bipartite graph K_{r,r} (with the sole exception of the complete graph K_4 for r=3.

(Unpublished work by Sokal and Jesus Salas show that this would give a bound of approximately 1.6\Delta(G).)

In other words, I believe that the largest chromatic root belongs to one of the smallest possible graphs!  Despite many years of attempting to disprove this,  and millions of chromatic polynomials computed and their roots extracted, I’ve never managed to find a single counterexample.

There are many other attractive conjectures regarding the bounds on chromatic roots, but I’ll leave them for future posts.

Open problems in “Finite Geometry”: Spreads of Hermitian varieties

Here is another problem in finite geometry that I personally find intriguing, but I’m sure many others in the community find is also one of the big-ish problems in our area. It concerns spreads of Hermitian varieties, and I guess this question goes back to Segre’s 200-page manuscript “Forme e geometrie hermitiane, con particolare riguardo al caso finito” (Forms and hermitian geometries, with particular regard to the finite case).

A Hermitian variety is one of the central objects in finite and algebraic geometry. We begin with a field F having an involutory automorphism \sigma, and an Hermitian matrix A; so A^\sigma=A^T (the transpose of A). Now consider the variety defined by the following equation

X^\sigma A X^T=0,\quad X=(X_1,X_2,\ldots,X_n).

So for example, we could have F=\mathbb{C} and \sigma being complex conjugation. We could take A to be the identity matrix and we would obtain the simplest Hermitian variety. We will now consider non-degenerate Hermitian varieties, where A is invertible, and let us suppose now that F is a finite field. So now F has square order q^2 and \sigma is nothing other than the map x\mapsto x^q. It turns out that for a given dimension and order of the finite field, any pair of non-degenerate Hermitian varieties are isometric; that is, if they are defined by the matrices A_1 and A_2, then there is an invertible matrix P such that P^\sigma A_1 P^T=A_2. So from now on, we will denote the non-degenerate Hermitian variety of PG(n-1,q^2) by H(n-1,q^2).

Continue reading “Open problems in “Finite Geometry”: Spreads of Hermitian varieties”

Why are there no maximal arcs of odd order?

A projective plane is a point/line incidence geometry that satisfies the following conditions:

  • Every two points lie on a unique line
  • Every two lines meet in a unique point
  • There is a quadrangle (four points, no three of which are collinear)

The last condition is just a non-degeneracy condition to eliminate trivial cases such as a single line containing all the points, and I’ll also add that I am only concerned here with finite projective planes. In this case it is easy to show that there is a number s such that there are s^2+s+1 points, s^2+s+1 lines, each line contains s+1 points, each point lies in s+1 lines; this special number s is called the order of the plane. In design theory language a projective plane is just a 2-(s^2+s+1,s+1,1) design.

The “canonical example” of a projective plane is the Desarguesian plane PG(2,q) whose point set is the set of 1-dimensional subspaces of the vector space V = GF(q)^3 and line set is the set of 2-dimensional subspaces of V. The order of PG(2,q) is q and since there is a field GF(q) for every prime power q, there is a projective plane of every prime power order. Probably the main open question in finite geometry is

Is there a finite projective plane whose order is not a prime power?

One thing that makes this problem difficult is that there are many many projective planes known other than PG(2,q) – lots of infinite families and plenty of  examples of small order – but they all resolutely have prime power order. (For those interested, Eric Moorhouse keeps comprehensive lists of small order planes.) If PG(2,q) were the only projective plane that was known, then we would conclude that the combinatorial definition of a projective plane was somehow so restrictive that it could only be met by the algebraic structure of a field. However, many of the known projective planes appear to have nothing much to do with fields and so the whole question is more subtle than just the existence of a field – in particular, what is it about projective planes that forces the orders of the fields to occur but dispenses with the fields themselves! The observant reader will notice that I am writing as though it is obvious that the answer to the question is “No” but, while this is what I personally believe, there are many geometers much more talented than I who believe the opposite, and spend at least some “Friday afternoon time” looking for planes of order 12 or 20 or 56 or whatever.

Maximal Arcs

Much more is known about the orders for which projective planes may or may not exist, but this is all written down elsewhere and today I want to discuss a less well-known problem, which is the existence of maximal arcs in projective planes. A maximal arc is a subset \mathcal{K} of the points of a projective plane such that every line that meets \mathcal{K} does so in the same number of points. In other words, there is a number n such that every line of the plane contains either 0 of n points of \mathcal{K} – we call this a set of type (0,n). Some simple counting shows that if a plane of order s contains a set of type (0,n) then n must divide s. [Edit: as JB points out, we should insist that n be strictly less than s.]

So when does these sets of points actually occur? For planes of even order the answer is pretty simple – the Desarguesian plane PG(2,2^h) contains a set of type (0,n) for every possible value of n that satisfies the necessary condition. Computer searches on the planes of order 16 show that most of them contain sets of type (0,n).

For planes of odd order, the situation is very different – not a single maximal arc in any projective plane of odd order is known. Often if there is an even-odd dichotomy of this sort, there is a parity argument hiding somewhere, but in this case nobody has managed to find one. However it is known that the Desarguesian plane PG(2,q) with q odd does not contain any maximal arcs. This was proved by Ball, Blokhuis and Mazzoca (paper here) who gave a very algebraic proof based on properties of the field underlying PG(2,q).

But what about the other planes? If it really is the case that maximal arcs do not exist in any projective plane of odd order, then this is a combinatorial statement for which we would really like a combinatorial proof. On the other hand, if it is only the algebra of PG(2,q) that prevents a maximal arc appearing there, then surely we should be able to find an example in some of the hundreds of thousands of known non-Desarguesian planes!

So this leads us to the main problem:

Find a maximal arc in a non-Desarguesian plane of odd order, or give a combinatorial reason why they cannot exist.

Yet another interesting number theory question

Q: Let n be an integer not divisble by 3. Suppose that p=n^2+n+1 is a prime and 2^{n+1}\equiv 1 \pmod{p}. Is n a power of 2?

A solution to this problem would imply that every finite flag-transitive projective plane is Desarguesian. Walter Feit obeserved this in his 1990 paper in the Proceedings of the American Mathematical Society, and he confirmed by computer that it is true for n\le    14,400,008. Since then, there has been some review and survey of this problem by various authors, and I’m surprised to see that none have sat at the computer and tried to extend Feit’s computation.

So I gave it a crack myself:

The answer is “Yes” for n \le 30,000,000.

This can definitely be extended by far better programmers than me … any advance on this bound?

Up ↑