Search Results

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. …

The Kneser graph $KG_{n,k}$ is the graph on $k$-subsets of $\{1, \dots, n\}$ with two subsets made adjacent when they are disjoint. The formula $$\chi(KG_{n,k}) = n - 2k + 2$$ was proved by Lovász in …

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line? Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0 …

I would like to add some more examples and references for the so called polynomial method that can help us recognise when it can be applied. From what I understand so far, the polynomial method fall …

Bannai, Bannai and Stanton proved that $f_d(k) \leq {d + k \choose k}$ in 1983. See: http://link.springer.com/article/10.1007%2FBF02579288 I don't think this bound has been improved in general. It is …

It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$. For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ …

A partial linear space (or a linear hypergraph) is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear …

Not much is known for the general case. Let $m(k, n, q)$ denote the minimum size of an $k$-blocking set in $AG(n, q)$. Trivially we have $m(0, n, q) = q^n$ and $m(n, n, q) = 1$. By Jamison/Brouwer-S …

See Section 4 in "On Zeros of a Polynomial in a Finite Grid" to see how Schwartz-Zippel lemma and many similar results on zeros of polynomials work for arbitrary commutative rings as long as the "grid …

Andries Brouwer's collection of strongly regular graphs: http://www.win.tue.nl/~aeb/graphs/srg/srgtab.html Eric Moorhouse's collections of finite projective planes and generalized polygons: http://eri …

Every finite geometry (projective planes, generalized polygons, polar spaces, near polygons, etc.) and every block design (Witt design, difference sets, Steiner triple systems, etc.) is a hypergraph. …

We are given a $0$-$1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0$-$1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or $\mathbb{Z …

Here are some examples where the dimension of a vector space of polynomials is used to solve a combinatorial problem. Theorem 1 There are at most $n(n+1)/2$ equiangular lines in $\mathbb{R}^n$. Proof. …

Here is an improvement of the upper bound which I found in ``The polynomial method in Galois geometries'' by Simeon Ball. See page number 4. The known constructions are somewhat crude. For exampl …

It has been proved by Simeon Ball that for $k \leq p$, all $[n, k, n-k+1]_q$ codes are Reed-Solomon codes, where $q = p^h$. See Corollary 9.2 in the following paper: Ball, S. On sets of vectors of a …