Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

Associated with an $n \times m$ matrix $A=(a_{ij})$ is the $n$-homogeneous polynomial in $m$ variables: $$ P_A=\Prod_{i=1}^n ( \sum_{j=1}^m a_{ij}X_j). An assignment vector X=(x_1,\dots,x_m) clearly satisfies $P_A(X)$ non-zero if and only if the vector $AX$ admits no zero entry. The above provides an algebraic platform for some fundamental questions in Combinatorics to be restated. For example, if A is the incidence matrix of edges and vertices of a graph $G=(V={v_1,dots,v_n},E), then $P_A$ is the graph polynomial $P_G$, a proper coloring of G is a vector C of color for which P_G(C) is not zero. The vast body of knowledge about zeros of polynomials, located at the very core of algebra, is hence a potential contributor to the study of graph coloring and related problems in graph theory and Matroid theory.