4
$\begingroup$

In a paper on Hadwiger's conjecture, https://web.math.princeton.edu/~pds/papers/hadwiger/paper.pdf, Seymour explains various results on excluding the complete graph as a minor.

In particular, there is a nice bound on the number of edges, due to Mader, as follows:

If $t\leq 7$ and $n\geq t-2$ then every $K_t$-minor free graph $G$ on $n$ vertices has $$ |E(G)|\leq (t-2)n-\frac{(t-1)(t-2)}{2}.$$

(The obvious application to Hadwiger, as Seymour describes, is that this bound controls the average degree and hence gives low minimum degree to which you can use induction to get a colouring result.)

Sadly the pattern fails for $t\geq 8$. Jorgensen and then Song and Thomas describe the exceptions explicitly for $t=8$ and $t=9$ respectively but as far as I can see no larger $t$ is understood. To be more precise Jorgensen's result says that if there is no $K_8$-minor and the displayed inequality fails then the exact number of edges is known and $G$ can be built from $K_{2,2,2,2,2}$ in a simple way (by "pure 5-sums").

However, in general the average degree in a $K_t$-minor free graph can be large - Kostochka, Thomason, ... - so the "exceptions" will get really bad for large $t$.

I'm interested in this from a slightly different perspective. Are explicit descriptions known (or potentially tractable) of $K_t$-minor free graphs for general $t$ provided that $n$ is quite small relative to $t$?

So a desired result would be something like:

For any natural number $t$ and any $t-2\leq n \leq 2t$, every $K_t$-minor free graph $G$ on $n$ vertices has $$ |E(G)|\leq (t-2)n-\frac{(t-1)(t-2)}{2},$$ unless $G$ is ... some exceptions like those in Jorgensen/Song and Thomas ...

If this is somehow easy then replace the vertex bound of $2t$ with something bigger.

$\endgroup$

1 Answer 1

4
$\begingroup$

There is no known straightforward answer, but pseudorandom graphs must come into the answer. See the paper by Myers and Thomason.

[In response to the comment below] Look at recent papers by Postle--Norine--Song, plus earlier work by Reed--Kawarabayashi, all on Hadwiger's Conjecture. You will see that the difficulty with K_t-minor-free graphs often occurs when the number of vertices is small when compared to t. In particular, for a suitable choice of c a random graph with ct sqrt(log t) vertices has no K_t minor. This says that small K_t minor-free graphs are wild! Another important conjecture (of Seymour and Thomas) is that the above edge bound does hold for sufficiently large highly connected graphs. Here "sufficiently large" is essential, otherwise random graphs provide counterexample.

$\endgroup$
2
  • $\begingroup$ Thanks. Could you elaborate a bit though? I glanced at the paper by Myers and Thomason but it's extremal - my question is wondering if restricting the number of vertices, in terms of the size of the minor, makes things sufficiently easier for general complete graphs that something nice can be said. $\endgroup$
    – user62562
    Commented Aug 13, 2020 at 14:03
  • $\begingroup$ Thanks. Given the info in the edit, I've accepted the answer. For the application I had in mind it's bad news but Norine-Postle-Song's Theorem 2.2 (of Woodall) might help instead. $\endgroup$
    – user62562
    Commented Aug 15, 2020 at 12:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.