14
$\begingroup$

Alon's (or Alon and Tarsi's?) combinatorial nullstellensatz is a powerful algebraic tool with many applications in combinatorics and number theory. See this, this, this and this mathoverflow question.

I am looking for good examples of results that were proved using combinatorial nullstellensatz (or its generalisation) but have no other known proof.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You can start with the 3-choosability of bipartite planar graphs. I don't know of any other proof (but maybe nobody looked for such a proof since the Alon Tarsi paper) $\endgroup$
    – Louis Esperet
    Commented Jun 9, 2015 at 13:21
  • $\begingroup$ @Louis: Thanks. That looks like a good candidate. $\endgroup$
    – Anurag
    Commented Jun 9, 2015 at 14:04
  • 1
    $\begingroup$ @LouisEsperet if I am not mistaken, there exists a combinatorial proof using the kernel technique (for all bipartite graphs with outdegrees at most $m$ and coloring with $m+1$ colors.) $\endgroup$
    – Fedor Petrov
    Commented Mar 20, 2019 at 9:04
  • $\begingroup$ You're completely right, thank you. $\endgroup$
    – Louis Esperet
    Commented Mar 20, 2019 at 10:30

1 Answer 1

Reset to default
5
$\begingroup$

Here is an example of a nice problem for which no combinatorial proof seems to be known. It is related to a problem studied in this paper https://arxiv.org/abs/1612.08698

Let $G$ be a $d$-degenerate graph (i.e. each subgraph contains a vertex of degree at most $d$). A classical result in graph theory is that if each vertex is given a list of $d+1$ colors, then every vertex can choose a color from its list such that the resulting coloring is proper.

Now, assume instead that each vertex of $G$ is given a list of size $d+1$ colors, except one vertex which has a list of size $d$. It can be proved with the combinatorial nullstellensatz that in this case again, each vertex can be colored with a color from its list, such that the resulting coloring of $G$ is proper (see the paper above, where a stronger result is proved when $d+1$ is prime, but the proof actually works in the weaker setting for general $d$).

I have worked on finding a combinatorial proof of this result, and I know several other researchers in the area who have studied this problem, without success.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .