Algebra in Combinatorics

There is no real unifying theme here except the word "algebra", which is sometimes linear, sometimes commutative, sometimes basic...

• On the rank of higher inclusion matrices (with C. Grosu, Y.Person), submitted.


• Exact k-wise intersection theorems, (with V.H. Vu), Graphs and Combinatorics, 21 (2005), 247-261.
  We prove the precise k-wise extension of several classical intersection theorems, for example the famous Oddtown Theorem. The original Oddtown Theorem states that if F is a family of subsets of an n element base set X with the properties that the cardinality of each subset is odd, while the pairwise intersections are even, then F has at most n members. The proof of this result relies on the simple observation that the inner product of the characteristic vectors of two subsets is the cardinality of their intersection. However, when the pairwise intersection property is exchanged to k-wise, we don't have a corresponding natural concept from linear algebra grabbing the meaning of k-wise intersection. In our proof, combinatorial ideas are mixed with the linear algebra technique. We obtain the precise answer when k-1 is equal to a power of 2. For other k we are extremely close but still there is a small gap.


• On the spectrum of projective norm-graphs, Information Processing Letters, 86 no. 2. (2003) 71-74.
  In this note the spectrum of the projective norm-graphs is calculated precisely, by observing that all eigenvalues are (possibly signed) Gaussian sums. The second eigenvalue is as small as it can be (asymptotically the square root of the degree). so the projective norm-graphs are as pseudorandom as it gets. Now this is hardly a great shock, as algebraically defined graphs are pseudorandom more often than not. It is rather the elementary method providing exact values which stands in great contrast with other algebraic constructions where deep theorems of Algebra or Algebraic Geometry are called upon for an estimation of the eigenvalues.


• Norm-graphs: Variations and Applications, (with N. Alon and L. Rónyai) Journal of Combinatorial Theory, (Series B), 76 (1999), 280-290.
  A followup to the first norm-graph paper. It contains an improvement over the original norm-graphs: the projective norm-graphs. These graphs do not contain K_t,(t-1)!+1 and, having cn^2-1/t edges, are as dense as possible. The number of edges in the K_3,3-free projective norm-graphs are slightly more than in the classical K_3,3-free construction of Brown, and for t=3 the algebra used is really very basic. Several applications to Ramsey-theory and discrepancy theory is also included.


• Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs, (with L. Babai, A. Gál, J. Kollár, L. Rónyai and A. Wigderson) Proc. of the twenty-eighth Annual ACM Symposium on the Theory of Computing (STOC), (1996), 603-611.
  The conference version of the norm-graph paper. It contains an application in the field of computational complexity. The model of monotone span programs is a linear algebraic model for computing monotone Boolean functions. The power of this model is demonstrated by exhibiting a function computable by a monotone span program in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae. On the other hand, explicit functions are constructed which require a superpolynomial size span program. Two approaches are described, both algebraic: the first utilizing norm-graphs, the second applying Paley-type bipartite graphs and deducing it's appropriate properties through Weil's character sum estimates.


• Norm-graphs and Bipartite Turán Numbers (with J. Kollár and L. Rónyai), Combinatorica, 16 (1996), no. 3, 399-406.
  An algebraically defined family of graphs, the so-called norm-graphs are introduced. They are given by high-degree equations over finite fields. Norm-graphs do not contain the complete bipartite graph K_{t, t!+1} as a subgraph and are very dense, in fact essentially as dense as possible, containing cn^2-1/t edges. Such a construction was not known earlier for t>3. The construction relies on ideas from algebraic geometry. The proof of the key lemma in the paper uses elementary commutative algebra.


• Dense Graphs with Cycle Neighborhoods (with Á. Seress), Journal of Combinatorial Theory (Series B), 63 (1995) 281-293.
  As long as the use of finite fields and their basic properties could be referred to as "algebra" this paper belongs to this category. We construct graphs, which locally look like a planar triangulation: the induced neighborhood of every vertex is a cycle. Still, these graphs are amazingly dense: the number of edges is almost quadratic, n^{2-ε (n)} where ε(n) tends to 0. It is known that such graphs cannot have cn² edges, by Szemerédi's Regularity Lemma.