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.
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
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 Kt,(t-1)!+1 and, having
cn2-1/t edges, are as dense as possible.
The number of edges in the K3,3-free projective norm-graphs are
slightly more than in the classical K3,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
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),
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 Kt, t!+1
as a subgraph and are very dense, in fact essentially as dense as
possible, containing cn2-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
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,
n2-ε (n) where ε(n) tends to 0.
It is known that such graphs cannot have cn2 edges, by
Szemerédi's Regularity Lemma.
Last modified: Sun Jun 30 22:40:52 CEST 2013