Transversals and relaxed colorings of graphs with
bounded degree
Normgraphs and Zarankiewicz problem
Other extremal problems
There are two related topics here; in both we are given a graph
of bounded maximum degree.
I: An adversary picks a partition of the vertex set into classes of
predescribed sizes and
we must select a transversal (i.e. one vertex of each part)
such that the subgraph induced on it has some "nice" structure.
How large should the parts of the partitions be such that we succeed
no matter what the adversary does?
A basic example is a theorem of Haxell, which claims that if the part sizes
are at least two times the maximum degree than one can select
an independent transversal. Besides having several applications, the study
of independent transversals inspired numerous completely different
approaches utilizing not only combinatorial but probabilistic or
topological ideas.
II: In the second line of problems one would like to color the
graph such that each monochromatic component is small,
i.e. its order is less than a constant
(depending only on the maximum degree and not the graph!).
This concept generalizes the usual concept of proper coloring.

Bounded transversals in multipartite graphs
(with R. Berke, P. Haxell),
Journal of Graph Theory 70(2012) 318331.

Deciding relaxed twocolorability  a hardness jump
(with R. Berke),
Combinatorics, Probability, and Computing, 18
(2009), 5381.
An extended abstract appeared in
Proc. 14th Annual European Symposium on Algorithms (ESA),
(2006) 124135.

Relaxed twocoloring of cubic graphs (with R. Berke),
Journal of Combinatorial Theory (Series B), 97 (2007),
652668.
An extended abstract appeared in
European Conference on Combinatorics, Graph Theory,
and Applications (EUROCOMB) (2005) 341344.

Odd independent transversals are odd, (with P. Haxell)
Combinatorics, Probability and Computing,
15 (2006) 193211.
We resolve a problem of Bollobás,
Erdős and Szemerédi about independent
transversals. For arbitrary positive integers n and r
we determine the largest integer Δ=Δ(r,n),
for which any rpartite graph with partite sets of size n
and of maximum degree less than Δ
has an independent transversal.
This value was known for all even r. Here we determine the value
for odd r and find that Δ(r,n)=Δ(r1,n). Informally
this means that the addition
of an odd^{th} partite set does not make it any harder to
guarantee an independent transversal.
In the proof we establish structural theorems which could be of independent
interest. They work for all
r>6, and specify the structure of slightly suboptimal graphs for
even r >7.

Extremal problems for transversals in graphs with bounded degree,
(with G. Tardos),
Combinatorica, 26 (2006) 333351.
We resolve the problem of Bollobás,
Erdős and Szemerédi about independent
transversals in rpartite graphs (see the above paper) for even r by
constructing rpartite graphs of relatively low degree containing no
independent transversal.
We also elaborate on the triangulation method of Aharoni and Haxell.
We investigate several problems of the following type. For a graph property P
what is the smallest part size p(d,P) which still guarantees that
a transversal inducing a subgraph with property P can be selected
from any partitioned graph of maximum degree d.
Some of the interesting results:
If the part sizes are at least d, then there is a forest transversal.
If the part sizes are at least (1+1/r)d then there is a transversal
which induces acyclic components of order at most r. Is (1+1/r)d best
possible? We only know that d1 isn't.
It would be very interesting to decide what's the truth
for matching transversals, i.e., when r=2.

Bounded size components  partitions and transversals,
(with P. Haxell, G. Tardos),
Journal of Combinatorial Theory, (Series B),
88 no.2. (2003) 281297.
We deal with a relaxation of the usual proper coloring. Instead of
requiring monochromatic components of order one, we let them
to be of constant order.
We prove that every 5regular graph can be two colored such that all
monochromatic components are bounded by 17671. Alon, Ding, Oporowski and
Vertigan showed that a similar statement cannot be true for 6regular graphs.
For every constant C they exhibited a 6regular graphs for which any
twocoloring produces a component of order at least C.
An intriguing problem remains open for kcolorings. What is the asymptotical
value of Delta(k) where Delta(k) is the largest integer, for which there is
a constant C such that any Delta(k)regular graph can be kcolored with
monochromatic components of order at most C.
We know that Delta(2)=5 and Delta(3)=8 or 9. We also know that
Delta(k)/k is at most 4 and for large k it is greater than 3.00001.
Where is the truth?
The Turán number ex(n,H) of a graph H is the largest integer e such that
there exists a graph on n vertices with e edges which does not contain H as
a subgraph. The asymptotic behavior of ex(n,H) is well understood if the
chromatic number of H is at least three.
Our knowledge is very sparse though for
bipartite H. A very old and notorious open problem is to determine
the Turán number of complete bipartite graphs (a slightly different but
very much related question is the socalled Zarankiewicz problem).
The conjectured order of
magnitude of ex(n, K_{t,s}) is n^{21/min{t,s}},
coming from the fifty year old
upper bound of Kővari, T. Sós and Turán.
The problem is open already for K_{4,4}.

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).
This implies that the normgraphs provide a constructive lower bound of
n^{4/3}(1+o(1)) for the Ramsey number r(C_{4}, K_{n}).
Similar bound was given earlier by Alon. Also, Alon and Rödl obtained our
result independently and used it to prove surprisingly tight bounds
on asymmetric multicolor Ramsey numbers of complete bipartite graphs.

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.

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.

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

How many colors guarantee a rainbow matching?
(with R. Glebov, B. Sudakov), submitted.

On conflictfree coloring of graphs
(with R. Glebov, G. Tardos),
submitted.

The Local Lemma is tight for SAT
(with H. Gebauer, G. Tardos),
22nd Annual ACMSIAM Symposium on Discrete Algorithms (SODA)(2011), 664674.

On the minimum degree of minimal Ramsey graphs
(with P. Zumstein, S. Zürcher),
Journal of Graph Theory, 64(2010), 150164.

Vizing's Conjecture for chordal graphs
(with R. Aharoni)
Discrete Mathematics, 309
(2009), 17661768.

Turán's theorem in the hypercube
(with N. Alon, A. Krech),
SIAM Journal on Discrete Mathematics, 21
(2007), 6672.

Exact kwise intersection theorems, (with V.H. Vu),
Graphs and Combinatorics,
21 (2005), 247261.
In this paper 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 nelement 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.
Here we generalize this and other classical statements
for kwise intersection instead of pairwise.
We put the emphasis on obtaining exact results, as these are relatively
scarce in extremal combinatorics.
In our proof, combinatorial ideas are mixed with linear algebra
technique. We obtain the precise answer when k=3 or 5 or more generally if
k1 is a power of 2. In other cases, say when k=4, we get extremely close
but don't quite get there...

A multidimensional generalization of the ErdősSzekeres lemma on
monotone subsequences, (with G. Tardos),
Combinatorics, Probability and Computing,
10 (2001), 557565.
An extension of the Monotone Subsequence Lemma of Erdős and Szekeres is
investigated, which arose from a possible application in real analysis.
(Namely from the problem of M. Laczkovich, whether any compact set of
positive Lebesgue measure in dspace admits a contraction onto a ball.)
Let {v^{1}, ... , v^{ n}} be a set
of vectors in dspace. Assuming the points are in general enough position
each pair uniquely determines an orthantpair where their differences lie.
A subset S of the vectors is called hyperplanelike for an
orthant pair (A,A) if A does not contain the difference of any
two elements of S.
We are interested in that how large "hyperplanelike" subset are we
guaranteed to find in any set of n ddimensional vectors.
Firstsightintuition would vote for cn^{11/d}.
Here we construct vector sets where this number is
much smaller, close to n^{12/d}.
In particular, our 3dimensional vector set contains no hyperplanelike
subset larger than cn^{5/8}.
The problem of the correct order of magnitude remains open already in 3D.
(For 2D the problem is equivalent with the ErdősSzekeres Lemma.)

Intersection Properties of Subsets of Integers,
European Journal of Combinatorics,
20 (1999), 429444.
This paper is about extremal combinatorics on the integers.
Let N_{k} be the largest integer such that one can select
N_{k}
subsets of the first n positive integers such that the pairwise
intersection of any two of them is an arithmetic progression of
length at least k. The value of N_{k} was determined exactly for
k=0 by Graham, Simonovits and T. Sós, and asymptotically for k> 1
by Simonovits and T. Sós.
For N_{1} however a large gap remained.
The main reason for this difficulty is that for N_{1}
there are two completely different type of constructions,
both nearly extremal. One of them is the family of threeelement
subsets containing a fixed integer, the other one consists of only
long arithmetic progressions.
The paper proves that N_{1} is asymptotically
n^{2}/2 and that the
extremal system must be "mixed". i.e., not purely one of the two basic types.

On Nearly Regular Cocritical Graphs,
Discrete Mathematics,
160 (1996) 279281.
A graph G is called (K_{3}, K_{3})cocritical if there
is a twocoloring of
the edges of G with no monochromatic triangle, but the addition of any
edge destroys this property. The notion, due to J. Nesetril, has its
roots in Ramseytheory. This short note improves on earlier results
by Galluccio, Simonovits and Simonyi by explicitely constructing
(K_{3}, K_{3})cocritical
graphs with maximum degree O(n^{3/4}).
As the trivial lower bound is of order n^{1/2}, a huge gap
remains.

Dense Graphs with Cycle Neighborhoods (with Á. Seress),
Journal of Combinatorial Theory (Series B),
63 (1995) 281293.
A planar triangulation has 3n6 edges. How many edges can a graph have if
we only require that it is a planar triangulation locally, i.e., the
neighborhood of each vertex is an (induced) cycle? Well, according to
this paper it could have surprisingly many.
We construct graphs with n^{2ε(n)} edges
where ε(n) tends to 0. Szemerédi's Regularity Lemma implies that
quadratic number of edges are not possible. (Clark, Entringer, McCanna,
Székely)
Last modified: Sun Jun 30 22:36:47 CEST 2013