Title: Erdös-Hajnal Sets and Semigroup Decompositions

Define a set of lines in $R^3$ to be ``stacked'' with respect to $v \in R^3$ if, from a vantage point far away in the direction of $v$, the lines are linearly ordered by the ``crossing over'' relation. Given a collection of skew lines and a point $v$, we ask, what is the largest stacked subset that must be present among the lines? This question, which appears in a a 2000 paper of Erdos, Hajnal, and Pach, is intimately related to the well-known Erdos-Hajnal conjecture via the Milnor-Thom theorem. It was recently resolved by a powerful and very general theorem of Alon, Pach, Pinchasi, Radoicic, and Sharir. We describe these results and discuss several related issues, including a generalization to ``Erdos-Hajnal sets'' and an intriguing problem concerning the decomposability of semi-algebraic sets: Do all semi-algebraic sets belong to the set algebra generated by semigroups in $R^d$? Our main result is a resolution of this question in dimensions 1 and 2.

Title: Locally Consistent Constraint Satisfaction Problems

An instance of a constraint satisfaction problem is k-consistent if any k constraints of it can be simultaneously satisfied. For a set P of constraint types, r_k(P) denotes the largest ratio of constraints which can be satisfied in any k-consistent instance composed by constraints from the set P. We study the asymptotic behavior of r_k(P) for sets P consisting of Boolean predicates. The limit r(P) of r_k(P) for k tending to the infinity is determined for all such sets P. Moreover, we design a robust deterministic algorithm (for a fixed set P of predicates) running in time linear in the size of the input and 1/x which finds either an inconsistent set of constraints (of size bounded by the function of x) or a truth assignment which satisfies the fraction of at least r(P)-x of the given constraints. Most of our results hold for both the unweighted and weighted versions of the problem.

During the talk, I will also survey related results on locally consistent SAT formulas and pose several open extremal problems on graph homomorphisms that are related to generalizing our results to sets P of arbitrary constraints.

Joint work with Zdenek Dvorak and Ondrej Pangrac.

Title: 0-1 matrices and the number of unit distances

At most how many edges can an ordered graph of $n$ vertices have if it does not contain a fixed forbidden ordered subgraph $H$? It is not hard to give an asymptotically tight answer to this question, unless $H$ is a bipartite graph in which every vertex belonging to the first part precedes all vertices belonging to the second. In this case, the question can be reformulated as an extremal problem for zero-one matrices avoiding a certain pattern (submatrix) $P$. We disprove a general conjecture of F\"uredi and Hajnal related to the latter problem, and replace it by some weaker alternatives. We verify our conjectures in a few special cases when $P$ is the adjacency matrix of an acyclic graph and discuss the same question when the forbidden patterns are adjacency matrices of cycles. Our results lead to a new proof of the fact that the number of times that the unit distance can occur among $n$ points in the plane is $O(n^{4/3})$. Joint work with G. Tardos.

Title: How different can two intersecting families be?

To measure the difference between two intersecting families $\F,\G \subseteq 2^{[n]}$ we introduce the quantity $D(\F ,\G)=|\{ (F,G):F \in \F, G \in \G, F\cap G =\emptyset \}|$. We proove that if $\F$ is $k$-uniform and $\G$ is $l$-uniform, then for large enough $n$ $\F_0=\{F \subseteq [n]: 1 \in F, n \notin F,|F|=k \}$ and $\G_0=\{G \subseteq [n]: 1\notin G, n \in G, |G|=l\}$ are optimal families (that is $D(\F,\G) \leq D(\F_0,\G_0)$ for all uniform $\F$ and $\G$), while in the non-uniform case $\F'_0=\{F \subseteq [n]: 1 \in F, n \notin F \}$ and $\G'_0=\{G \subseteq [n]: 1\notin G, n \in \G\}$ are optimal for any $n$.

Title: Minimal Universal Bipartite Graphs

A graph U is (induced)-universal for a class of graphs X if every member of X is contained in U as an induced subgraph. We study the problem of finding a universal graph with minimum number of vertices for various classes of bipartite graphs: exponential classes of bipartite graphs, bipartite chain graphs, bipartite permutation graphs, and general bipartite graphs. For general bipartite graphs, we present a construction, which is asymptotically optimal, while for the other classes our solutions are optimal in order.

Title: Forbidden Configurations

We survey the latest development in forbidden configurations. The result of Balog and Bollob\'as on unavoidable traces of set systems raised the question how to determine $\mathrm{forb}(\mathcal{F},n)$, where $\mathcal{F}$ is a family of forbidden 0-1 matrices. We show the next step and provide a counter-example for (an unstated but plausible) conjecture.

Title: Regularity Lemmas for Hypergraphs

Recently, W.T. Gowers, and V.Rodl and J. Skokan have developed Regularity Lemmas and corresponding Counting Lemmas for $k$-uniform hypergraphs. A Counting Lemma estimates the number of subhypergraphs of given isomorphism type in an appropriate collection of dense and regular blocks provided by the corresponding Regularity Lemma.

In this talk we discuss some new developments in this area. In particular, we focus on techniques for overcoming technical difficulties arising in "typical" applications of the Rodl-Skokan-Lemma.

This is joint work with V. Rodl.

Title: Local chromatic number and the Borsuk-Ulam theorem

The local chromatic number of a graph, introduced by Erdos, Furedi, Hajnal, Komjath, Rodl, and Seress in 1986, is the minimum number of colors that some vertex is guaranteed to see in its closed neighbourhood if the vertices of the graph are properly colored. It is obviously bounded from above by the chromatic number and was recently proven to be bounded from below by the fractional chromatic number. We study the local chromatic number of such graphs where these two bounds lie far apart. Prime examples of such graphs are Kneser graphs, Schrijver graphs, and (generalized) Mycielski graphs. The chromatic number of most of these graphs can be determined using the Borsuk-Ulam theorem. We prove tight or almost tight bounds for the local chromatic number of many of these graphs. In particular, we show that the local chromatic number of an appropriately large t-chromatic Schrijver graph for fixed odd t equals (t+3)/2. The lower bound can be obtained by applying Ky Fan's generalization of the Borsuk-Ulam theorem. The upper bound is combinatorial. The results are joint with Gabor Tardos.

Title: Ramsey number of hypergraph cycles

For two fixed graphs $G$ and $H$, the Ramsey number $r(G,H)$ is the smallest integer $N$ such that every red-blue coloring of the edges of the complete graph with $N$ vertices contains a red copy of $G$ or a blue copy of $H$. This number has been studied for a number of different pairs $(G,H)$ of graphs and one of the initial results determined its value when both $G$ and $H$ are cycles.

In this talk we discuss this problem for the hypergraph cycles.

Title: On a problem of Erd\H{o}s and Rothschild

An old question of Erd\H{o}s and Rothschild from 1979 asks which graph $G$ on $n$ vertices has the most $2$-edge-colourings with no monochromatic $r$-clique. Clearly the colouring is unrestricted when $G$ is $K_r$-free, so they made the natural conjecture that the largest complete $(r-1)$-partite graph of order $n$ gives the most colourings. For $r=3$ this was proved by Yuster, but the general case of $r>3$ remained open.

In this talk we present a proof of Erd\H{o}s-Rothschild conjecture and show that the same result also holds for $3$-edge-colourings. Somewhat surprisingly, this is no longer true when there are at least $4$ colours; we have constructions that do exponentially better than the natural example.

The proofs are based on Szemeredi's regularity lemma together with some additional tools in extremal graph theory, and provide a rare example of a precise result proved by applying this lemma.

This is joint work with N. Alon, J. Balogh and P. Keevash

Title: Co-degree Density of Hypergraphs

Given a family F of r-uniform hypergraphs, the classical Turan theory studies the maximum proportion of r-sets an n element set can have without containing F. This limit, as n becomes large, is sometimes called the Turan density of F. We consider the related problem of determining the (normalized) maximum possible minimum co-degree that the family of r-sets in an n element set can have without containing F. As n goes to infinity, this approaches a limit which we call the co-degree density of F, and write g(F).

For each r>1, let G_r = {g(F): F is a family of r-graphs}. Our main result is that for each r>2, G_r is dense in [0, 1). This is in stark contrast to the fact that G_2 = {0, 1/2, 2/3, 3/4..}, a fact that follows from the Erdos-Simonovits-Stone theorem. This phenomenon is similar to the existence of real numbers that are not jumps in hypergraphs, proved by Frankl and Rodl. Several other results about co-degree densities are provided parallel to those of the classical Turan theory.

This is a joint work with Dhruv Mubayi.