Today I put a toe into the pool that is MathOverflow for the first time.

My question was:

Which graphs have the property that the number of i-vertex induced subgraphs is at most i for some i<n/2 (where n is the number of vertices)?

To avoid cases I am not interested in, I want the graph to be connected and non-bipartite and its complement to have the same properties.

Of course every graph has this property for i=2, and every triangle-free graph (or complement of one) for i=3. What about larger values of i?

The question is here.

Here I would like to expound at slightly greater length.

The question arose from thinking about a problem of João Araújo, which itself comes from semigroup theory. But the problem itself is purely about permutation groups. Classically, we say that a permutation group is ihomogeneous if, given any two i-element subsets of the domain, there is an element of the group carrying one to the other. Now we make a new definition: the group is (i,i+1)-homogeneous if, given an i-set I and an (i+1)-set J, there is a permutation mapping I to a subset of J.

Which permutation groups of degree n, with n ≥ 2i+1, are (i,i+1)-homogeneous but not i-homogeneous?

Computation suggests that there are just five such permutation groups:

  • the cyclic and dihedral groups of order 5, with n=5, i=2;
  • the 1-dimensional affine group over GF(7), with n=7, i=3;
  • the groups ASL(2,3) and AGL(2,3), with n=9, i=4.

Certainly there are no others of degree at most 20.

At first I was sure that this problem would have a short and elegant solution; but the five exceptions gave me pause. So finally I engaged my brain to see what I could do.

Let G be a permutation group of degree n with this property. There are a few things that are straightforward:

  • if i=2, then only the two exceptions of degree 5 arise;
  • G is transitive;
  • G is primitive;
  • G has at most i orbits on i-sets, so that its order is at least {n choose i}/i;
  • G has at most three orbits on 2-sets;
  • if G is 2-homogeneous it is 2-transitive.

So the proof strategy is:

  • reduce 3 to 1 in the fifth property (so that G is 2-homogeneous);
  • go through the list of 2-transitive groups to determine all further exceptions.

The fourth property suggested a possible approach to the proof of 2-homogeneity. If G is not 2-homogeneous, then it preserves a graph (indeed, the set of all pairs is partitioned into three G-invariant graphs). Each of these is primitive, and clearly each has diameter at least 3. Moreover, the fourth property says that each of these graphs has at most i induced subgraphs on i vertices, up to isomorphism.

I recollected that there are results saying that graphs usually have many induced subgraphs; but the only results I could find, by Erdős and Hajnal, and by Alon and Bollobás, are asymptotic, with constants like 10-21 in them, so unlikely to be helpful here.

So I posed the question on MathOverflow.

Now some conditions are required to rule out obviously silly graphs such as stars which have only two induced subgraphs on i vertices for any i. So I required that the graph and its complement should both be connected and non-bipartite (these certainly hold in my case). But the result was an object lesson. Doug Stones came up with an example. The strategy is to take a graph like a star, and add just a small perturbation to it to ensure that it satisfies my conditions. So the conditions have to be strengthened to rule such things out. Maybe the best strategy would have been to put all the cards on the table in the first place. But in fact there are probably more interesting things to say without putting on all my conditions, so maybe it was for the best.

Impressions of MathOverflow: I like the way that MathJax works on the site; I hope to get around installing it myself someday … But I am not all that happy with the competitive spirit of earning points, badges, etc., which is not really why I do mathematics. Finally I am very impressed with the speed at which several people jumped in and engaged with the problem!

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics, mathematics and tagged , , , . Bookmark the permalink.

8 Responses to MathOverflow

  1. Qiaochu Yuan says:

    Regarding points, badges, etc. the issue was extensively discussed on meta when Emmanuel Kowalski made similar remarks.

    • Extensively is the word… I am not particularly bothered by it, but the statement that badges measure how much the community trusts you seems particularly inappropriate in mathematics. I convince you by showing you a proof, or pointing you to where you can find one.

      What worries me (though not enough to make me lose any sleep) is the fact I discussed in my post on impact factors, that when a measure becomes a target it is no longer useful as a measure.

      • Qiaochu Yuan says:

        “Measure” is perhaps too strong a word (and I would say that applies only very roughly to reputation and not very much to badges). Nobody’s using badges or reputation in a performance evaluation. I just think of it as a cute way to trick my brain into doing more mathematics; I don’t take it too seriously, and I don’t think anyone else does either.

      • Peter says:

        I don’t think the points and badges are designed to show you how much the mathematical research community trusts an MO user but how much the mathoverflow community trusts an MO user.

        In that sense I find them absolutely useful. At the very least they are a very good measure of activity — for better or worse if you look at some undergrads…

        I would rather judge people by their MO profile than their h-index. It’s much more transparent.

  2. Peter says:

    Peter, if you allow me one more comment. Would you consider

    a) linking to your question here
    b) linking to this post on your question (say, as a comment)
    c) tagging this post “PlanetMO” so that it can be found on ?

    I think that’d be excellent for people looking to learn more about your question (and your writing here).

  3. Peter says:

    Thanks for the tags, Peter.

  4. I have succeeded in the first step of the programme. So it is just a case of checking the 2-transitive groups now. Of course, this means that my poor MathOverflow problem is now an orphan, and has to make its own way in the world. I think there is something interesting there, but it is necessary to think a bit harder about what the right conditions (to make an interesting problem) are.

  5. Pingback: Graphs with few induced subgraphs – Math Solution

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.