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 kwise intersection theorems, (with V.H. Vu),
Graphs and Combinatorics,
21 (2005), 247261.
We prove the precise kwise 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 kwise, we don't
have a corresponding natural concept from linear algebra grabbing
the meaning of kwise intersection.
In our proof, combinatorial ideas are mixed with the linear algebra
technique. We obtain the precise answer when k1 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 normgraphs,
Information Processing Letters,
86 no. 2. (2003) 7174.
In this note the spectrum of the projective normgraphs
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 normgraphs 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.

Normgraphs: Variations and Applications,
(with N. Alon and L. Rónyai)
Journal of Combinatorial Theory, (Series B),
76 (1999), 280290.
A followup to the first normgraph paper. It contains an
improvement over the original normgraphs: the projective normgraphs.
These graphs do not contain K_{t,(t1)!+1} and, having
cn^{21/t} edges, are as dense as possible.
The number of edges in the K_{3,3}free projective normgraphs 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 Ramseytheory 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 twentyeighth Annual ACM
Symposium on the Theory of Computing (STOC),
(1996), 603611.
The conference version of the normgraph 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 normgraphs, the second applying Paleytype bipartite
graphs and deducing it's appropriate properties through
Weil's character sum estimates.

Normgraphs and Bipartite Turán Numbers
(with J. Kollár and L. Rónyai),
Combinatorica, 16 (1996), no. 3, 399406.
An algebraically defined family of graphs, the socalled
normgraphs are introduced.
They are given by highdegree equations over finite fields.
Normgraphs 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^{21/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) 281293.
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^{2} edges, by
Szemerédi's Regularity Lemma.
Last modified: Sun Jun 30 22:40:52 CEST 2013