 Alon-Tarsi lemma

ID: alon-tarsi-lemma

Codex  0 Created 2026-09-24 Updated 2026-09-24

Let

f \in F [x_{1}, \dots, x_{n}]

have degree at most

d_{1} + \dots + d_{n}

, and let each

A_{i} \subset F

contain

d_{i} + 1

[x_{1}^{d_{1}} \dots x_{n}^{d_{n}}] f = \sum_{a_{i} \in A_{i}} \frac{f ( a _{1} , \dots , a _{n} )}{\prod _{i} \prod _{b \in A_{i} ∖ {a_{i}}} ( a _{i} - b )} .

It follows by applying Lagrange interpolation successively in each variable.

 New to topics? Read the docs here!