12
$\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.

$\endgroup$
  • 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 Jun 9 '15 at 13:21
  • $\begingroup$ @Louis: Thanks. That looks like a good candidate. $\endgroup$ – Anurag Jun 9 '15 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 Mar 20 at 9:04
  • $\begingroup$ You're completely right, thank you. $\endgroup$ – Louis Esperet Mar 20 at 10:30
3
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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