The Fife Coastal Path

A week or so ago saw for me the end of a journey that had been in progress for more than twelve years.

I first walked a stretch of the Fife Coastal Path (St Andrews to Crail) on the free afternoon of the Groups St Andrews meeting in 2005. The weekend before last, I did the last remaining stretch, Kincardine to Ferry Toll via North Queensferry.

Start of Fife Coastal Path at Kincardine

The path goes most of the way around the Kingdom of Fife. (Incidentally, I am not quite sure why it is called this. It is true that Dunfermline was the royal capital of Scotland from the eleventh century until the Union of the Crowns in 1603 when it moved to Edinburgh; but they were kings of Scots, not of Fife. Much earlier, when the Romans came to Britain, they recorded the names of the tribes inhabiting Scotland; Fife was the home of the Venicones, one of the peoples who later made up the Pictish nation, but I don’t think it was in any sense a kingdom.) But the Kingdom of Fife lies between the wide firths of the rivers Forth and Tay, and the path goes along the edge of both of them as well as the coastline between, right around the Kingdom except for the relatively short land border with Perth and Kinross.

Longannet Power Station

The stretch along the Forth estuary from Kincardine to Inverkeithing is a real mixture, ranging from the ugly (the road to the Rosyth ferry probably the worst, and three stretches on the A985 were not inspiring) to fascinating. The old town of Culross (the l is silent) with palace, town hall, abbey, and more. I mentioned here the talk by Alex Craik about the St Andrews mathematician William Welwood, whose plan to siphon water out of coal mines would clearly not have worked for the mine in Culross, which extended under the sea!

Culross Palace

We walked this stretch west-to-east. First up was Longannet: the name may mean something like “field of the church with relics”, but all has been covered by a large coal-fired power station, now closed and awaiting demolition. Then lovely Culross and the Torry Bay nature reserve. On the busy road (with a small detour through Crombie, a village with little to recommend it but the view and the brief relief from the road), then into the attractive villages of Charlestown and Limekilns. This is the home of the Scottish Lime Centre Trust, an organisation providing information and training about building with limestone. Round the back of the Rosyth naval base, and under the new Queensferry Crossing, the road took us down to North Queensferry, and around the headland and up the hill to Ferry Toll, a bus interchange from which we were able to get the bus home.

Advertisements
Posted in geography, history | Tagged , , , , , , , , | 1 Comment

D’Arcy Thompson

D’Arcy Thompson’s celebrated book On Growth and Form was published 100 years ago.

To celebrate this and the fact that Thompson was Professor of Mathematics at St Andrews for 64 years (and had been at Dundee before that, for part of which time it was a campus of St Andrews), the University had a small meeting, culminating in a public lecture by Evelyn Fox Keller, which I attended.

Thompson was clear in his belief that the laws of biology did not contain any new principles beyond the laws of physics and mathematics. He was keen to explain biological development on the basis of mathematical laws. He also looked very carefully at things, a skill which perhaps some mathematical biologists don’t have to the same degree.

That is all I learned about Thompson from Keller’s lecture, which was more about the history of biology in the twentieth century. Thompson had the misfortune to be writing just as genetics was getting into its stride, and it seems that for a good part of the twentieth century, people believed that “the gene” was a biological principle, analogous to the atom (or the elementary particle) in physics, but not itself reducible to mathematics and physics. So Thompson’s work, at a stroke, became unfashionable. He wrote in On Growth and Form: “I know that in the study of material things number, order, and position are the threefold clue to exact knowledge: and that these three, in the mathematician’s hands, furnish the first outlines for a sketch of the Universe.”

I would naively have thought that the eludication of the structure of DNA strengthened Thompson’s position, since the geometry of the molecule and its interactions with things such as methyl radicals seem to be amenable to study by mathematics and physics, and we know now that these play an important part in the action of genes.

But I am afraid to say that the lecture did reinforce my belief that, on the whole, historians read papers whereas mathematicians put on a performance; moreover, the lecturer seemed to be unaware that she was giving a public lecture rather than just the closing lecture of a specialist conference, and she really was unaware that the printed text that she was reading omitted lines here and there.

Still, she can give me eleven years, so I suppose I should simply hope that I am still in the business when I reach her age.

You can read more about D’Arcy Thompson here, on the St Andrews History of Mathematics website.

Posted in events, history | Tagged , , , , | 1 Comment

Carnival of Mathematics 150

Episode 150 of the Carnival of Mathematics is now live, here on the CoDiMa blog.

Did you know that there are 150 groups of order 900? For what values of n is it true that the number of groups of order n divides n, and what are the possible quotients? (This is not a serious question.)

Posted in Uncategorized | Tagged , | Leave a comment

The history of computing

Today, the School of Computer Science at St Andrews put on this year’s Distinguished Lectures. The lecturer was Ursula Martin, and she spoke about the history of computing, or more precisely, “What every computer scientist should know about computer history”.

The lectures were held in the Byre Theatre, the third one in the presence of the Principal, Professor Sally Mapstone, herself a historian. It seems they were compulsory for undergraduates on certain courses; the auditorium was packed, with very few spare seats, despite the fact that relatively few staff from either Computer Science or Maths and Stats were there.

But I want to talk about the contents of the lectures, not the surroundings.

There were three lectures. The first two focussed on important people in the story, Charles Babbage and Ada Lovelace, Alan Turing and Grace Hopper. The third tackled two more nebulous topics: why did Ada Lovelace’s mathematical abilities polarise later commentators to the extent they did, and what happened to the women who were in Britain’s computing business in its early days?

The introductory slide was a “timeline of computing”; Ursula invited us to consider what was missing from it. As she said, the development of computing was certainly not a single and inevitable strand. For example, about the time that Tim Berners-Lee was inventing the World Wide Web, there was a possible rival called Gopher developed at the University of Minnesota. It lost out partly because the University took a hard line on intellectual property rights. But things might have been different …

Charles Babbage and Ada Lovelace

We began with a picture of the Great Exhibition of 1851, the profits of which still fund doctoral and postdoctoral positions. At the time, Britain was the hub of a vast empire. Running an empire requires mathematics, and a lot of calculation, much of which was done using log tables. Babbage wanted to make log tables “as cheap as potatoes”.

So he designed the Difference Engine Number 2, which used 31-digit numbers, and could compute 7th order differences (that is, fit degree 6 polynomials). His description of the Engine amounted to the invention of a hardware description language (in modern terms). He also proposed an Analytical Engine; it never got off the drawing board (or was even completely designed), but it was intended to be a general purpose computer (in the modern sense); it even conformed to von Neumann architecture (a single CPU, instructions and data fetched from memory). It was to be programmed using punched cards, an idea borrowed from weaving.

As is well known, Ada Lovelace wrote a 70-page paper which described how the Analytical Engine would work. Ursula showed us detailed diagrams of how it would solve two simultaneous linear equations, and (more difficult) how it would compute Bernoulli numbers using the recurrence relation (which she derived from the usual formula).

The program solving simultaneous linear equations reminded me very strongly of assembly language programming. You have to choose the register to store every intermediate result. High-level languages free us from those details!

Lovelace and Babbage (especially the former) also speculated more philosophically on the capabilities of the Engine. In Lovelace’s words, “the cards are able to reproduce all the operations which intellect performs in order to attain a determinate result”. On a generous interpretation, this says it can compute anything which can be computed, an idea taken up by Turing.

They also speculated on using the Engine to process non-numerical data. In this connection, Ursula showed us a page from the archives on which Babbage and Lovelace had been doodling about the Königsberg bridges and magic squares. These are two topics associated with Euler. In my mathematical quotes, you will find part of a letter Euler wrote to Carl Ehler, mayor of Danzig, on the Königsberg bridges, denying that this is mathematics (and, by extension, denying that topology is mathematics). So this is conceivably a case in point. I don’t know if there is any information on how the diagram of the bridges would be input to the Engine and what algorithm it would use to solve it. Probably they hadn’t got that far.

Lovelace also says “The machine can do whatever we know how to order it to perform”. In other words, it cannot be creative. Ursula thought this might have been her adopting a safe position in the theological arguments of the time.

In a curious footnote, a slightly cut-down version of the Difference Engine was built by the Swede Per Georg Scheutz, who even sold one to the British government.

Alan Turing and Grace Hopper

Turing quoted Lovelace’s remark about “all operations which intellect performs”. Unlike her, he argued that a human philosopher can do no more than this, and so a machine is just as capable of thinking as a human.

Turing also proposed getting the computer to correct and avoid bugs in a program, a precursor to Tony Hoare’s logic of computation.

Incidentally, it is claimed that Grace Hopper found the first bug; Ursula showed us the entry in the log saying “Moth in relay”.

Turing had a page in the manual of the Manchester computer devoted to getting the computer to play music, later realised (with Christopher Strachey) in a performance of “God save the Queen” and “In the Mood” (shockingly out of tune) which was broadcast on the BBC in the 1950s. Strachey also programmed it to write love poetry; we saw his doodle of a flowchart for this program.

Grace Hopper did far more than find the first bug. She wrote the first compiler, and designed the business computing language COBOL. More importantly, she realised (as the makers of the Manchester computer did not) that, in order to get businessmen to use computers, you had to do away with symbols, exponents and subscripts, and explain everything in clear plain words.

Other topics

In order to put the timeline of computing in its place, Ursula gave us a timeline of computing in India. The first computer in India was installed in 1955 (before the first computer in Scotland), and the first computer designed and built in India began operating in 1960.

She also showed us some events in the development of the Internet, to show that it was far from a single line of development; there were many other networks around at the time of ARPANET.

But the main focus of the third lecture was on two topics. First was Ada Lovelace’s mathematical education and ability. Apart from an early tutor who told her that the only way to be a mathematician was to memorise everything in the book, her real tutor was Augustus De Morgan, who had a clear idea of her abilities. He described it in terms of a young man with comparable abilities, since a woman could not study at Cambridge in those days. Such a person would never be Senior Wrangler (essentially, succeed in a problem-solving competition), but his grasp of the overall structure could lead to his becoming a very successful research mathematician.

But this comment was seriously misunderstood by later historians, even when they quoted it verbatim, as saying that Lovelace was too bogged down in details to succeed. People who should have known better claimed that she could not have understood what was written in her 70-page paper on the Analytical Engine. Her analysis of the Bernoulli numbers showed that she was no slouch as a mathematician.

A nice story concerns how she got the better of the tutor who had told her to memorise the contents of the book. After studying Pythagoras’ Theorem, she asked him how you would prove a similar theorem in which squares on the sides of the right-angled triangle are replaced by equilateral triangles. He hadn’t the faintest idea; it was not in the book! As Ursula says, either you see this as being very difficult, or you think it is quite simple.

Then she turned to the many women who had been important in the early days of British computing, who are now essentially unknown, written out of the script either by corporate policy (as in the case of the Civil Service, which had separate men’s and women’s career scales in those days) or by individual blindness. She showed us a web page showing the first professor of computing (named) at a university which I won’t name and shame, in front of the university’s new computer (named). There is also a woman sitting at the console, who was not even mentioned in the picture caption. At Ursula’s urging, her name was discovered (not so difficult, in fact) and added to the caption.

Conclusion

Ursula gave us two reasons for studying history:

  • understanding the past helps us grasp the present and think about the future (for example, the problems we are now facing may have arisen before);
  • the stories we tell (or don’t) shape who we are, what we do, and how we are seen.

The web page for the Distinguished Lectures Series is here. I do not know how to find the slides or the reading list. This material may be restricted to students.

Posted in events, history | Tagged , , , , | 3 Comments

Synchronization and all that, 2

The story I told in the last post is not over.

The recent development is that we spotted a mistake in the paper. An easy mistake to make: we had simply used the symbol n in two different places with different meanings, and then proceeded to get them confused.

The fix required arguments considerably longer than the ones we had given. The fact that we were able to fix the proof reasonably quickly shows the power of Delsarte’s ideas for studying association schemes. His thesis (published in the Philips Research Reports in 1973) is the foundation for much subsequent work in both coding theory and combinatorial design theory.

Anyway, in the course of this fix, we discovered that we had left out an example. This doesn’t affect our conjectures, which are asymptotic: they assert that, for fixed k, for large enough n,the symmetric group of degree n acting on k-sets is non-separating if and only if a Steiner system S(t,k,n) exists for some t with 0 < t < n.

The main change is that, for k = 4, “large enough” should mean “at least 10” rather than “at least 9”.

The reason is as follows. Consider the graph whose vertices are the 4-subsets of {1,…,9}, two vertices joined if they intersect in 1 or 3 points. Then the clique number and the chromatic number of this graph are both equal to 9; and hence S9 acting on the 135 vertices of the graph is non-synchronizing (as explained in the preceding post).

I leave as an exercise the proof that the graph has clique number 9. (Your job is to find nine subsets of {1,…9}, each of size 4, and having the property that any two meet in 1 or 3 points.)

The fact that the chromatic number is 9 was proved (in different language) by Breach and Street in 1988. They showed that the 4-subsets of a 9-set can be partitioned into 9 copies of the Steiner system S(3,4,8), each omitting one of the nine points. (They called such a configuration an “overlarge set” of Steiner systems, as opposed to a “large set”, where each Steiner system uses all of the points.)

Their proof, as I recall, was in part computational. But a couple of years later, Cheryl Praeger and I were able to give a conceptual proof, based on the remarkable geometric concept of triality, specifically over the field of 2 elements. Here is a brief summary. I restrict to the 2-element field, though much of this works for an arbitrary field.

Consider the quadratic form

x1x2+x3x4+x5x6+x7x8.

It defines a quadric consisting of 135 points of the 7-dimensional projective space over GF(2). The maximal subspaces contained in this quadric are “solids” (3-dimensional subspaces), and fall into two families, where two solids are in the same family if they intersect in a line or are disjoint, and in different families if they intersect in a plane or a point. There are 135 planes in each family. Also there are 1575 lines on the quadric.

Consider the quadric as an incidence structure, where the incidence between points, lines, and solids is inclusion, and two solids are incident if they intersect in a plane. (We regard incidence as a symmetric relation, so that a line is incident with a point if and only if the point is incident with the line.) It turns out that this structure has some additional, unexpected symmetries: we can permute cyclically the sets of points, solids in the first family, and solids in the second family, while preserving the family of lines and the incidence relation. This symmetry is the “triality” map on the quadric.

Now here is a concrete realisation of the quadric. As our 8-dimensional vector space V, we take all the binary words of length 9 with even weight. (These are the words orthogonal to the all-1 word with respect to the usual inner product, so they do form a subspace.) Now it can be shown that the function mapping v to half the weight of v mod 2 (that is, words of weight 0, 4 and 8 map to 0, words of weight 2 and 6 map to 1, in GF(2)) is a quadratic form on V, equivalent under linear transformation to the one given above. The quadric consists of the (9 choose 4)+(9 choose 8)=135 wordds of weight 4 or 8. The 9 words of weight 8 form an ovoid on the quadric, a maximal set of points with no pair lying on a line of the quadric. (The third point on the line joining two points of weight 8 has weight 2.) The stabiliser of the ovoid is the symmetric group S9, so by counting we find that there are 960 ovoids.

Applying the triality map turns an ovoid into a spread, a set of 9 pairwise disjoint solids (necessarily all from the same family) covering each point of the quadric.

Now what does a solid look like in our interpretation? It is a 4-dimensional vector subspace of V, all of whose elements have weight 4 or 8 (since it is contained in the quadric). It is easy to see that such a subspace must consist of the zero vector, a word of weight 8, and 14 words of weight 4 forming the blocks of a S(3,4,8) on the support of the word of weight 8. So each of the 9 solids in a spread contains one of the nine words of weight 8 and 14 of the 126 words of weight 4, and we have our large set of Steiner systems.

Now the classification up to isomorphism is found by writing down two beautiful examples (each with a doubly transitive automorphism group), counting how many copies of each there are (the index of its automorphism group in the symmetric group), and checking that these numbers add up to 1920 (the number of images of ovoids under the triality map and its inverse).

This was presented at the 1988 Italian combinatorics conference in the beautiful town of Ravello, and published in the conference proceedings. The publisher was a small outfit called the Mediterranean Press. I believe I heard a rumour that they were no longer in business. So, with Cheryl’s agreement, I have posted a scan of the paper here. (The paper by Breach and Street is in the Journal of Combinatorial Mathematics and Combinatorial Computing in 1988.)

A final note: this paper is also referred to in my notes On doing geometry in CAYLEY.

Posted in doing mathematics, exposition | Tagged , , , , , , , , | Leave a comment

EKR, Steiner systems, association schemes, and all that

A great number of mathematical problems amount to looking in a large but highly structured graph, and finding a complete or null subgraph of largest possible size there.

For a simple example, consider Latin squares of order n. One of these is an n×n array containing the entries 1,2,…,n, arranged in such a way that the entries in any row or any column are all distinct. So each row is a permutation of the numbers 1,2,…,n (in the nineteenth-century sense, that is, an arrangement of these numbers rather than the operation of rearranging them), and any two of the n permutations defined by all of the rows disagree in all positions. Thus, if we make a graph whose vertices are the permutations, two vertices joined if they agree in at least one position, then a Latin square is the vertex set of a null subgraph of maximum size.

I propose to speak about a class of graphs which includes some which give a context, in this way, to two big theorems of combinatorial mathematics: the construction of Steiner systems, and the Erdős–Ko–Rado theorem. Considering the whole class of graphs leads us to a conjecture which would extend (in some sense) both of these big results.

I’ll conclude with an even more general context for this, the theory of association schemes.

Steiner systems

The Lady’s and Gentleman’s Diary in 1844 published a problem which proved too difficult for its readers, and indeed was not solved for more than a century and a half. The problem was posed by the Editor, Wesley Woolhouse, and ran as follows:

Determine the number of combinations that can be made out of n symbols, p symbols in each; with this limitation, that no combination of q symbols, which may appear in any one of them, shall be repeated in any other.

We assume that q < p < n to make things interesting. But for my purposes later on, I will change notation, and use k and t instead of p and q.

There is an upper bound, C(n,t)/C(k,t), where C denotes the binomial coefficient. For the numerator is the number of subsets of size t; in a collection of combinations satisfying the problem, each combination contains C(k,t) of them, and there is no overlap. But, without giving a construction, it is not clear whether this upper bound can be attained (and indeed it cannot always be).

In the next issue, he specialised to the case k = 3, t = 2; that is, we are looking for a collection of 3-element subsets of {1,2,…,n}, with the property that no two meet in more than one point. In terms of our original formulation, if we make a graph whose vertices are the 3-element subsets, two subsets joined if they meet in two points, we are looking for the largest null subgraph of such a graph. The upper bound mentioned above reduces to n(n−1)/6, and it is easy to show that it cannot be attained unless n is congruent to 1 or 3 (mod 6). [This is an instance of what I shall call the divisibility conditions.] Thomas Penyngton Kirkman, rector of Croft in Lancashire, gave a proof that, if this is satisfied, then a set of n(n−1)/6 triples with the required property can be found. In such a system, any two points are contained in exactly one of the distinguished triples.

Such configurations are now called Steiner triple systems, even though Steiner didn’t pose the problem of their existence until six years after Kirkman had solved it! An article by Norman Biggs and Robin Wilson in Combinatorics: Ancient and Modern (Oxford University Press 2013) untangles some of the history.

Kirkman clearly found that his job as a clergyman didn’t use all his energy; as well as this, he worked on group theory, knot theory, and polyhedra, and was elected Fellow of the Royal Society in 1857.

In general, a configuration meeting the bound in Woolhouse’s original problem is called a Steiner system, and denoted by S(t,k,n). In the years from 1847 to 2014, a number of specific examples were found, none having t larger than 5. (Examples of S(5,6,12) and S(5,8,24) were found in the first half of the twentieth century; they are associated with the sporadic simple groups found by Émile Mathieu.) Then in 2014, Peter Keevash announced a proof that, for any k and t, if n satisfies the relevant divisibility conditions and n is “sufficiently large” (in terms of k and t), then a Steiner system S(t,k,n) exists.

Since Keevash’s work, at least one further proof has been given. But nobody knows exactly how large n has to be (except in special cases).

The Erdős–Ko–Rado Theorem

A collection of k-element subsets of a set of n points is called an intersecting family if any two of its members have a point in common. More generally, it is tintersecting if any two of its members have at least t points in common.

The question, What is the largest t-intersecting family of k-subsets of an n-set?, was tackled by Paul Erdős, Chao Ko, and Richard Rado in 1938. To understand what they did, first consider how you can obtain a large family. If we fix an element of the n-set, say 1, and take all the k subsets which contain 1, then clearly we get an intersecting family of size C(n−1,k−1). Indeed, if we choose all the subsets containing all of 1,2,…,t, we obtain a t-intersecting family of size C(nt,kt).

EKR, as I shall call them, showed that, provided n is sufficiently large (in terms of k and t), we cannot do better. Indeed, for intersecting families, this bound holds as long as n > 2k; and, if n > 2k+1, then the only families attaining the bound are those consisting of all the k-sets containing some fixed element.

Although this theorem was proved in 1938, it was not published until 1961. Paul Erdős said subsequently,

One of the reasons for the delay was that at the time there was relatively little interest in combinatorics. Also in 1938, Ko returned to China, I went to Princeton, and Rado stayed in England.

This result can also be put into our general framework. As we did before, form the graph whose vertices are the k-subsets of our n-set, two vertices joined if they have at least t points in common. We saw that Steiner systems come from null subgraphs of largest possible size; EKR families are complete subgraphs of largest possible size.

Comparison

However, there is an interesting contrast. In the case of Steiner systems, the bound is easy to establish, but a very complicated construction is required to build systems meeting the bound. In the EKR case, construction of the large systems is easy, but the proof that no larger family is possible is what requires the work!

Another thing to notice is that the product of the two bounds is

C(nt,ktC(n,t)/C(k,t) = C(n,k)

(a short exercise with binomial coefficients). The right hand side is the number of vertices of the graph. This reminds us of a property which symmetric graphs have:

If a graph on n vertices has automorphism group acting transitively on the vertices, then the product of the sizes of the largest complete and null subgraphs does not exceed the number of vertices of the graph.

This is a slightly more difficult exercise; it uses double counting, and two facts:

  • if a group G acts transitively on n points, then the number of elements of G mapping x to y is |G|/n (a consequence of Lagrange’s Theorem;
  • a complete and a null subgraph cannot have more than one vertex in common.

Now the graph in our example has C(n,k) vertices, and the symmetric group Sn acts transitively on the vertex set. This goes some way to “explaining” the relation between the two bounds, and also suggests that algebra has some part to play here.

(This is a small plug for a new book, Erdős–Ko–Rado Theorems: Algebraic Approaches, by Chris Godsil and Karen Meagher, recently published in the Cambridge Advanced Mathematics series.)

Thus Keevash’s Theorem says that, for this graph, if n is sufficiently large in terms of k and t, then the product of the sizes of the largest complete and null subgraphs of the graph is equal to the number of vertices if and only if the divisibility conditions are satisfied.

Generalisation

We can define a more general class of graphs whose vertices are the k-subsets of an n-set. All these graphs have the property that adjacency of vertices depends only on the size of the intersection of the subsets, and all of them admit the symmetric group acting vertex-transitively.

Let I be a subset of {0,1,…k−1}. We form a graph GI on the vertex set by letting two subsets be declared adjacent if the size of their intersection is an element of the set I. In the case where I = ∅ or I = {0,1,…k−1}, the graph GI is the null graph or the complete graph, respectively; we ignore these cases. Also we note that if I and J are complementary subsets of {0,1,…k−1}, then the graphs GI and GJ are complements of each other (the edges of one are the non-edges of the other). So we have (2k−2)/2 = 2k−1−1 complementary pairs of “interesting” graphs.

Among these graphs, those for which I = {t,…k−1} play a special role, as we have seen; the largest possible null subgraphs of these are Steiner systems, and the largest possible complete subgraphs are EKR families. Thanks to the theorems of EKR and Keevash, we know that, for n sufficiently large, the product of the sizes of the largest complete and null subgraphs in these graphs is equal to the number of vertices.

Here is the big conjecture, which appears in a paper of mine with Mohammed Aljohani and John Bamberg, accepted for publication in Portugaliae Mathematica in the last week of September this year:

There is a function F on the natural numbers such that, given k and n, if n ≥ F(k) and the graph GI defined above has the property that the product of the sizes of the largest complete and null subgraphs is equal to the number of vertices, then I or its complement is equal to {t,…k−1} for some value of t, and the divisibility conditions for a Steiner system S(t,k,n) are satisfied.

This was previously known for k = 2 and k = 3; in the paper, among other things, we prove it for k = 4, by a method which seems likely to generalise to larger values. Unfortunately, of course, the number of graphs we have to consider grows exponentially with k, as we saw.

The graph GI has the property that its edge set is the disjoint union of the edge sets of the graphs G{i} for i ∈ I. These graphs make up an association scheme. This means that their adjacency matrices commute and that their span over the real numbers is an algebra (that is, closed under multiplication).

Association schemes are very interesting combinatorial objects, with applications in group theory, computation, statistics, and elsewhere. But I will forbear to describe them further here, except to note that they provide a context for the problems described here, and asking similar questions in other association schemes leads to challenging research problems. Indeed, there are a number of inequalities for the sizes of complete and null subgraphs in terms of the eigenvalues of the matrices in the association scheme; and there are ways of computing these eigenvalues from counting information about the association scheme. In particular, the result that says that the product of complete and null graph sizes in any union of graphs in the association scheme is at most the number of points, irrespective if the scheme has any symmetry or not: transitivity on vertices is not necessary in this case.

An example

Although we conjecture that things are orderly when n is large, there are many fascinating examples not following this pattern for smaller n. Here is an example.

The Fano plane

The picture shows the famous Fano plane: seven points with seven 3-subsets, any two meeting in exactly one point. So it is a Steiner triple system S(2,3,7) (whose triples are called lines), and is also a complete subgraph of G{1}. Our general inequality that the product of complete and null subgraph sizes is at most the number of points shows that a null subgraph of G{1} has size at most 5.

There are null subgraphs of size 5: the EKR sets (all triples containing two given points give examples). But there are others with a completely different structures. Consider, for example, any line of the Fano plane together with the four 3-sets disjoint from it. Any two of these five sets meet in 0 or 2 points. (In the picture, 135, 137, 157, 357 and 246 is an example.)

Posted in exposition | Tagged , , , , , , | Leave a comment

Carnival of Mathematics

The Carnival of Mathematics, a monthly blogging round-up, will be hosted on the CoDiMa site in October. (It travels round various mathematics blogs but is coordinated by Katie at The Aperiodical.)

My contribution to the carnival is a piece called “EKR, Steiner systems, association schemes, and all that”, which will be posted here shortly.

Posted in events, the Web | Tagged , | Leave a comment