(Extremal) Graph Theory and other extremal problems

Transversals and relaxed colorings of graphs with bounded degree
Norm-graphs and Zarankiewicz problem
Other extremal problems

Transversals and relaxed colorings of graphs with bounded degree

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


• Deciding relaxed two-colorability --- a hardness jump (with R. Berke), Combinatorics, Probability, and Computing, 18 (2009), 53-81.
  An extended abstract appeared in Proc. 14th Annual European Symposium on Algorithms (ESA), (2006) 124-135.


• Relaxed two-coloring of cubic graphs (with R. Berke), Journal of Combinatorial Theory (Series B), 97 (2007), 652-668.
  An extended abstract appeared in European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB) (2005) 341-344.


• Odd independent transversals are odd, (with P. Haxell) Combinatorics, Probability and Computing, 15 (2006) 193-211.
  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 r-partite 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)=Δ(r-1,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 sub-optimal graphs for even r >7.


• Extremal problems for transversals in graphs with bounded degree, (with G. Tardos), Combinatorica, 26 (2006) 333-351.
  We resolve the problem of Bollobás, Erdős and Szemerédi about independent transversals in r-partite graphs (see the above paper) for even r by constructing r-partite 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 d-1 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) 281-297.
  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 5-regular 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 6-regular graphs. For every constant C they exhibited a 6-regular graphs for which any two-coloring produces a component of order at least C.
  An intriguing problem remains open for k-colorings. 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 k-colored 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?

Norm-graphs and the Zarankiewicz problem

• 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). This implies that the norm-graphs provide a constructive lower bound of n^4/3(1+o(1)) for the Ramsey number r(C₄, 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.


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


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

Other extremal problems

• 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 conflict-free coloring of graphs (with R. Glebov, G. Tardos), submitted.


• The Local Lemma is tight for SAT (with H. Gebauer, G. Tardos), 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)(2011), 664-674.


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


• Vizing's Conjecture for chordal graphs (with R. Aharoni) Discrete Mathematics, 309 (2009), 1766-1768.


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


• Exact k-wise intersection theorems, (with V.H. Vu), Graphs and Combinatorics, 21 (2005), 247-261.
  In this paper 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. Here we generalize this and other classical statements for k-wise 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 k-1 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ős-Szekeres lemma on monotone subsequences, (with G. Tardos), Combinatorics, Probability and Computing, 10 (2001), 557-565.
  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 d-space admits a contraction onto a ball.)
  Let {v¹, ... , v ⁿ} be a set of vectors in d-space. Assuming the points are in general enough position each pair uniquely determines an orthant-pair where their differences lie. A subset S of the vectors is called hyperplane-like 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 "hyperplane-like" subset are we guaranteed to find in any set of n d-dimensional vectors. First-sight-intuition would vote for cn^1-1/d. Here we construct vector sets where this number is much smaller, close to n^1-2/d. In particular, our 3-dimensional vector set contains no hyperplane-like subset larger than cn^5/8.
  The problem of the correct order of magnitude remains open already in 3-D. (For 2-D the problem is equivalent with the Erdős-Szekeres Lemma.)


• Intersection Properties of Subsets of Integers, European Journal of Combinatorics, 20 (1999), 429-444.
  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₁ however a large gap remained. The main reason for this difficulty is that for N₁ there are two completely different type of constructions, both nearly extremal. One of them is the family of three-element subsets containing a fixed integer, the other one consists of only long arithmetic progressions. The paper proves that N₁ is asymptotically n²/2 and that the extremal system must be "mixed". i.e., not purely one of the two basic types.


• On Nearly Regular Co-critical Graphs, Discrete Mathematics, 160 (1996) 279-281.
  A graph G is called (K₃, K₃)-cocritical if there is a two-coloring 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 Ramsey-theory. This short note improves on earlier results by Galluccio, Simonovits and Simonyi by explicitely constructing (K₃, K₃)-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) 281-293.
  A planar triangulation has 3n-6 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)