Title: Hamiltonian cycles in Dirac graphs

We prove that any graph with minimum degree at least $n/2$ has at least $n!/(2+o(1))^{n}$ Hamiltonian cycles. This bound confirms a conjecture of G. Sarkozy, S. Selkow, and E. Szemeredi. Key ingredients in the proof include entropy and martingales.

Joint with J. Kahn.

Title: Graph properties recognizable by number of homomorphisms from restricted classes of graphs

We study the properties of graphs that can be determined just from a knowledge of numbers of homomorphisms from a fixed class of graphs ${\cal H}$. A well known result of Lovasz shows that if ${\cal H}$ consists of all graphs, the numbers of homomorphisms uniquely determine the graph, and hence also all its properties. We characterize some smaller classes ${\cal H}$ with this property. We also consider classes ${\cal H}$ that do not determine the graph uniquely, and study properties like bipartiteness or connectivity that sometimes still can be deduced from the numbers of homomorphisms.

Title: Bounding the partition function of spin-system

Let $\Lambda =\{\lambda_i:1\leq i \leq m\} \cup \{\lambda_{ij}:1\leq i \leq j \leq m\}$ be a system of non-negative reals. For any graph $G$, $\Lambda$ induces a natural probability distribution on $\{f:V(G)\rightarrow [m]\}$ in which each such $f$ is given weight $\prod_{v \in V(G)} \lambda_{f(v)} \prod_{u,v \in E(G)} \lambda_{f(u)f(v)}$ and is chosen with probability proportional to its weight. (This framework encompasses many familiar statistical physics spin-models such as Potts, Ising and hard-core.)

With Prasad Tetali, we considered the normalizing constant (or partition function) of the above-described distribution, in the case when all $\lambda_{ij}\in\{0,1\}$, and we obtained an upper bound that is tight for the class of regular bipartite graphs. Here we use random graphs to extend this work to the case of general non-negative $\lambda_{ij}$.

Title: The circular chromatic index of graphs of high girth

Colorings of graphs form a prominent topic in graph theory. Several relaxations of usual colorings have been introduced and intensively studied. In this talk, we focus on circular colorings of line graphs. A proper circular k-edge-coloring, for a real k>=1, is a coloring by real numbers from the interval [0,k) such that the difference modulo k of the colors c_1 and c_2 assigned to incident edges is at least one, i.e., 1 <= |c_1-c_2| <= k-1 .

A classical theorem of Vizing states that the edges of every graph G with maximum degree D can be colored by at most D+1 colors so that no two incident edges have the same color, i.e., the chromatic index of G is at most D+1. We show that for every e>0 there exists g such that the circular chromatic index of a graph G with maximum degree D whose girth is at least g does not exceed D+e. Note that the index must be at least D because the line graph of such graph G contains a clique of order D.

Our research is motivated by a conjecture of Jaeger and Swart 1979 (that turned out to be false) that high girth cubic graphs have chromatic index three. Our results imply that the conjecture is true when relaxed to circular colorings: the circular chromatic index of high girth cubic graphs is close to three.

One of the ingredients of our proof are recent results on systems of independent representatives and hypergraph matchability of by Aharoni, Haxell, Meshulam and others, which we also briefly survey during the talk.

(joint work with Tomas Kaiser, Riste Skrekovski and Xuding Zhu)

Title: Bounding the number of edges in permutation graphs

Recently Adin and Roichman introduced two types of graphs constructed from permutations and posed the problem of finding the maximum number of edges in such graphs. In this talk we show how to determine the maximum number of edges in one of these graphs and characterize all permutations which achieve this maximum. We also discuss some remaining open problems.

Joint work with P. Keevash and B. Sudakov

Title: Laplacians, Homology and Hypergraph Matchings

We'll discuss some connections between the expansion constant of a graph and the topology of certain complexes associated with the graph. Applications include a lower bound on the homological connectivity of the independence complex, in terms of a new graph domination parameter defined via vector representations of the graph. This in turn implies Hall type theorems for matchings in hypergraphs.

Joint work with R.Aharoni and E. Berger.

Title: Small separations in symmetric graphs

The study of expansion in vertex transitive graphs and in groups divides naturally into the study of local expansion, or connectivity, and the study of global expansion (the growth). The expansion properties of a group are those of its Cayley graphs, and vertex transitive graphs are a more general setting.

There are a number of classic results concerning local expansion in vertex transitive graphs. For instance, a result of Mader shows that every finite connected $d$-regular vertex transitive graph is $d$-edge-connected. This result was refined by Lovasz and Watkins who proved that if $S$ is a $d$-edge-cut in a simple finite connected vertex transitive graph of degree $d$ and $A$ is the smallest component in $G \setminus S$, then either $A$ is a singleton, a clique of size $d$ (which forms a block of imprimitivity), or $d=2$ (so the graph is a cycle) and $A$ is a path. There are analogues of the above theorems for digraphs and vertex cuts.

Some new results, a joint work with Matt DeVos, about local expansion in vertex transitive graphs will be presented. They are also meaningful for groups, and have some asymptotic applications. The goal is to prove a rough structure theorem for small cuts which is close in spirit to the Lovasz-Watkins result. Our main theorem gives rough structure of vertex-cuts of bounded size in arbitrary vertex transitive graphs.

Title: Some bounds on the circular chromatic number of sparse graphs

A graph is called sparse if its maximum average degree is between 2 and 3. We give some bounds on the circular chromatic number of sparse graphs. Precisely we prove that sparse graphs with a given maximum average degree have homomorphisms to some circular cliques.

Title: On a restricted cross-intersection problem

Suppose A and B are families of subsets of an n-element set and L is a set of s integers. We say that the pair (A,B) is $L$-cross-intersecting if the intersection size of every member of A with every member of B belong to L. Among such pairs (A,B) we write P_L(n) for the maximum possible value of |A||B|. In this talk we present an exact bound for P_L(n) when n is sufficiently large, improving earlier work of Sgall. We also discuss several intriguing open problems.

This is joint work with P. Keevash.

Title: Diameters of duals are linear

For every oriented tree $T$ there exists a graph $D_T$ (called the \emph{dual} of $T$) such that $T \not\rightarrow G \Leftrightarrow G \rightarrow D_T$ holds for every $G$ (an arrow denotes the existence of a homomorphism). An explicit construction of $D_T$ has been found recently. Although the $D_T$ constructed this way may have exponential number of vertices in $|V(T)|=n$, we will prove that its diameter is linear in $n$ (and therefore $D_T$ is "small" in some sense).

Title: Random matrices: Questions and Answers

I will give a brief survey on random matrices with discrete distributions, with main focus on the random sign matrix (and its parameters such as determinant, singularity, eigenvalues etc).

Joint work with Terence Tao and some with Kevin Costello.