The polynomial degrees of Grassmann and Segre varieties over GF(2)

A recent proof that the Grassmannian G1,n,2G1,n,2 of lines of PG(n,2)PG(n,2) has polynomial degree n2-1 is outlined, and is shown to yield a theorem about certain kinds of subgraphs of any (simple) graph Γ=(V,E)Γ=(V,E) such that |E|<|V||E|<|V|. Somewhat similarly, the polynomial degree of the Segre variety Sm,n,2,m⩽nSm,n,2,m⩽n, is shown to be mn+mmn+m, and in consequence a graph theory result is obtained about certain subgraphs of any graph ΓΓ which is a subgraph of the complete bipartite graph Km+1,n+1Km+1,n+1.