The first reference to the rigidity of frameworks in the mathematical literature occurs in a problem posed by Euler in 1776. Consider a polyhedron $P$ in 3-space. We view $P$ as a `panel-and-hinge framework' in which the faces are 2-dimensional panels and the edges are 1-dimensional hinges. The panels are free to move continuously in 3-space, subject to the constraints that the shapes of the panels and the adjacencies between them are preserved, and that the relative motion between pairs of adjacent panels is a rotation about their common hinge. The polyhedron $P$ is rigid if every such motion results in a polyhedron which is congruent to $P$. Euler's conjecture was that every polyhedron is rigid. The conjecture was verified for the case when $P$ is convex by Cauchy in 1813. Gluck showed in 1975 that it is true when $P$ is `generic' i.e. there are no algebraic dependencies between the coordinates of the vertices of $P$. Connelly finally disproved the conjecture in 1982 by constructing a polyhedron which is not rigid. I will describe results and open problems concerning the rigidity of various other types of frameworks. I will be mostly concerned with the generic case for which the problem of characterizing rigidity usually reduces to pure graph theory.

Several algorithmic meta-theorems state that certain logically defined graph problems have FPT (Fixed-parameter Tractable) or XP algorithms for graph parameters that measure the width of certain hierachical decompositions of the input graphs. The lectures will review the known results for the cases where problems are expressed by MSO (Monadic Second-order), and the automata based tools for constructing the corresponding algorithms.

Main topics:

1) The automata accept algebraic terms that denote the input graphs and represent their decompositions witnessing bounds on tree-width or clique-width.

2) There are several constructions of finite automata from MSO formulas. These automata yield FPT algorithms. The construction presented in the lectures has been successfully implemented (by I. Durand, LaBRI), so as to produce fly-automata.

3) Finite automata arising from MSO formulas are in most cases too large to be built in the traditional way, as lists of states and of transitions. To the opposite, in a fly-automaton, states are described and not listed, and transitions are computed only when needed.

4) Fly-automata can have infinite sets of states: their states may include counters. Hence, they can check properties that are not MSO expressible. Equipped with output functions, these automata can compute counting and optimizing functions on graphs. They can be constructed by programs from logical expressions of properties and functions that extend MSO logic.

Rather than new algorithmic results, we present tools for constructing easily certain dynamic programming algorithms by combining predefined automata for basic functions and properties.

References:

B.C. & J. Engelfriet: Graph structure and monadic second-order logic, Cambridge University Press, 2012.

B.C. & I. Durand: Automata for the verification of monadic second-order graph properties, J. Applied Logic, 10 (2012) 368-409.

B.C. & I. Durand : Computing by fly-automata beyond MSOL, May 2013, submitted.

The euclidean distortion of a finite, metric space $X$, measures how much the metric is distorted under embeddings of $X$ into Hilbert space. A celebrated result of Bourgain (1984) says that the distortion of $X$ is at most logarithmic in the number of points of $X$. Families of expander graphs demonstrate that this bound is sharp. (Linial-London-Rabinovich 1995). For finite, connected, graphs $X$, we prove that the euclidean distortion is bounded below by the square root of the normalized spectral gap, times the displacement of $X$ (that is, the maximal displacement of permutations of vertices of $X$). This inequality allows to give unified proofs for computations of euclidean distortion for cubes (Enflo 1969), cycles (Linial-Magen 2001), and expanders. It also allows for non-trivial lower bounds on distortion for some non-expanding families of regular graphs, e.g. Cayley graphs of $SL_n(p)$ ($p$ fixed, $n$ varying). This is joint work with Pierre-Nicolas Jolissaint.

A prism is a graph made of three vertex-disjoint paths linking two disjoint triangles. A pyramid is a graph made of three paths, disjoint except at one of their end x, linking x to the three vertices of a triangle. A theta is a graph made of three paths, disjoint except at their ends. A wheel is a graph made of a cycle plus a vertex that has at least three neighbors in the cycle. (Warning: there are also technical requirement on the lengths of the path not worth detailing in an abstract). A Truemper configuration is a graph isomorphic to either a prism, a pyramid, a theta, or a wheel. It turned out that the induced subgraphs of a graph that are isomorphic to a Truemper configuration are very important in structural graph theory. For instance, they play a key role in the proof of the strong perfect theorem, in the structure of even-hole-free graphs, claw-free graphs, and several other classes. We will show several properties of classes of graphs defined by excluding Truemper configurations. In particular, we will present results proved jointly with Aboulker, Charbit and Vuskovic, showing how lex-BFS generates an order of the vertices with interesting properties when applied to graphs where well chosen Truemper configurations are excluded.

In this talk, I will discuss a relation between the coarse Ricci curvature notion introduced by Ollivier and the number of odd cycles on a finite graph. This is an analogue to the fact that on Riemannian manifolds, lower Ricci curvature bound controls overlaps of two balls. Applying this curvature notion to $t$-neighborhood graphs (kind of coarse representations of the original graph), I will discuss properties of a sequence of lower curvature bounds $k[t]$ and their applications to estimates of the spectrum of normalized graph Laplace operator. This is joint work with Frank Bauer and Juergen Jost.

Often local structural properties, such as an existence of a vertex or an edge with particularly structured neighborhood, can be used to construct efficient algorithms or prove other useful properties of hereditary graph classes. In this talk we survey several hereditary classes of graphs for which local structural properties are obtained by decomposition.

Spectral geometry concerns the interplay between spectral properties of Laplacians and geometric properties of the underlying structures. For manifolds and graphs with uniformly bounded vertex degree the theory is rather well understood. Recent years have seen an increasing interest in graphs with unbounded vertex degree. Spectral geometry of such graphs leads to unexpected features. It turns out that these can - to a certain extent - be explained via the concept of intrinsic metric. In fact, a corresponding theory can even be developed in the framework of Dirichlet forms. This framework encompasses both Laplacians on graphs and Laplacians on manifolds. We will give an introduction into this circle of ideas and survey some recent results.

Several algorithmic meta-theorems state that certain logically defined graph problems have FPT (Fixed-parameter Tractable) or XP algorithms for graph parameters that measure the width of certain hierachical decompositions of the input graphs. The lectures will review the known results for the cases where problems are expressed by MSO (Monadic Second-order), and the automata based tools for constructing the corresponding algorithms.

Main topics:

1) The automata accept algebraic terms that denote the input graphs and represent their decompositions witnessing bounds on tree-width or clique-width.

2) There are several constructions of finite automata from MSO formulas. These automata yield FPT algorithms. The construction presented in the lectures has been successfully implemented (by I. Durand, LaBRI), so as to produce fly-automata.

3) Finite automata arising from MSO formulas are in most cases too large to be built in the traditional way, as lists of states and of transitions. To the opposite, in a fly-automaton, states are described and not listed, and transitions are computed only when needed.

4) Fly-automata can have infinite sets of states: their states may include counters. Hence, they can check properties that are not MSO expressible. Equipped with output functions, these automata can compute counting and optimizing functions on graphs. They can be constructed by programs from logical expressions of properties and functions that extend MSO logic.

Rather than new algorithmic results, we present tools for constructing easily certain dynamic programming algorithms by combining predefined automata for basic functions and properties.

References:

B.C. & J. Engelfriet: Graph structure and monadic second-order logic, Cambridge University Press, 2012.

B.C. & I. Durand: Automata for the verification of monadic second-order graph properties, J. Applied Logic, 10 (2012) 368-409.

B.C. & I. Durand : Computing by fly-automata beyond MSOL, May 2013, submitted.

A (finite) graph may be made into a metric graph by assigning lengths to the edges. The space of all such assignments on a given graph (suitably normalized) is, in some sense, an analogue of the moduli space of a Riemann surface. The moduli space supports the so-called Weil-Petersson Riemannian metric, which has been much studied. In this talk, we shall propose a analogue of the Weil-Petersson metric in the graph case and discuss some of its properties. Our definition is motivated by a "thermodynamic" approach introduced by Curt McMullen. This is joint work with Mark Pollicott.

This is joint work with Eran Makover, Björn Mützel, Mika Seppälä and Robert Silhol. Consider a family of compact Riemann surfaces given by Fenchel Nielsen parameters, where k of the length parameters go to zero and all other parameters are kept fixed. The Jacobians then tend to the Jacobian of the limit surface. In the lecture we show that this gives rise to a concept of Jacobians for finite graphs which should allow one to investigate certain phenomena in a simple computational setting. The Jacobians proposed here have twice the expected dimension and obey the Kirchhoff rules of electric circuits.

Motivated by results on the existence of spectral gaps for Laplacians on Riemannian coverings we analyze the spectrum of periodic discrete and metric graphs. We discuss first the notion of Laplacians for discrete and metric graphs and mention some spectral relations between these operators. We localize the spectrum of the Laplacians within certain bands and give sufficient conditions for the existence of spectral gaps. For this we will need a bracketing procedure for eigenvalues on a fundamental domain of the periodic structure. We conclude mentioning some examples where both, the discrete and the quantum graph, have spectral gaps. [Joint work with O. Post: J. Math. Anal. Appl. 348 (2008) 806-833 and Rev. Math Phys. 20 (2008) 199-231.]

I will review several examples where techniques motivated by ideas in Partial Differential Equations and Differential Geometry lead to interesting results about difference equations on graphs, most notably the combinatorial Laplacian. Examples will include the maximum principle, Harnack inequality, Cheeger's inequality and a recent result about surjectivity of combinatorial Laplacian for infinite graphs.

Spectral geometry concerns the interplay between spectral properties of Laplacians and geometric properties of the underlying structures. For manifolds and graphs with uniformly bounded vertex degree the theory is rather well understood. Recent years have seen an increasing interest in graphs with unbounded vertex degree. Spectral geometry of such graphs leads to unexpected features. It turns out that these can - to a certain extent - be explained via the concept of intrinsic metric. In fact, a corresponding theory can even be developed in the framework of Dirichlet forms. This framework encompasses both Laplacians on graphs and Laplacians on manifolds. We will give an introduction into this circle of ideas and survey some recent results.

Several algorithmic meta-theorems state that certain logically defined graph problems have FPT (Fixed-parameter Tractable) or XP algorithms for graph parameters that measure the width of certain hierachical decompositions of the input graphs. The lectures will review the known results for the cases where problems are expressed by MSO (Monadic Second-order), and the automata based tools for constructing the corresponding algorithms.

Main topics:

1) The automata accept algebraic terms that denote the input graphs and represent their decompositions witnessing bounds on tree-width or clique-width.

2) There are several constructions of finite automata from MSO formulas. These automata yield FPT algorithms. The construction presented in the lectures has been successfully implemented (by I. Durand, LaBRI), so as to produce fly-automata.

3) Finite automata arising from MSO formulas are in most cases too large to be built in the traditional way, as lists of states and of transitions. To the opposite, in a fly-automaton, states are described and not listed, and transitions are computed only when needed.

4) Fly-automata can have infinite sets of states: their states may include counters. Hence, they can check properties that are not MSO expressible. Equipped with output functions, these automata can compute counting and optimizing functions on graphs. They can be constructed by programs from logical expressions of properties and functions that extend MSO logic.

Rather than new algorithmic results, we present tools for constructing easily certain dynamic programming algorithms by combining predefined automata for basic functions and properties.

References:

B.C. & J. Engelfriet: Graph structure and monadic second-order logic, Cambridge University Press, 2012.

B.C. & I. Durand: Automata for the verification of monadic second-order graph properties, J. Applied Logic, 10 (2012) 368-409.

B.C. & I. Durand : Computing by fly-automata beyond MSOL, May 2013, submitted.

Each incomplete-block design for $v$ treatments in $b$ blocks gives rise to a Levi graph (with $b+v$ vertices) and a concurrence graph (with $v$ vertices). The various criteria that statisticians use to assess the quality of the design are related to familiar graph concepts: number of spanning trees, electrical resistance, edge-connectivity, and so on. Sometimes calculations are easier for the Levi graph than for the concurrence graph. Sometimes nice classes of graphs, such as regular graphs or distance-regular graphs, give mathematically satisfying results but not necessarily the best block design to use in practice.

14:30 Cathedral Guided Tour

16:15, 16:30, 16:45 Lindisfarne Gospels - ticket price 6.50

This research is a byproduct of some results in the classification of certain finitely generated infinite groups that are amalgams of finite groups. They are closely related to groups of Kac- Moody type, that is groups of automorphisms of țwin buildings. Affine groups of Kac-Moody type have many interesting quotients and the corresponding Cayley graphs provide uniform series of expanders. This is joint work with R Blok and A Vdovina.

The spectrum of a graph is the multiset consisting of the eigenvalues of its adjacency matrix. The spectrum is an invariant of the graph, and since checking whether two graphs are cospectral is easy (polynomial), it is an interesting question how often this invariant determines the graph. Relatively few graphs are know to be determined by their spectrum, and there exist many examples of nonisomorphic cospectral graphs. Nevertheless, the speaker conjectures that almost all graphs are determined by their spectrum. In the lecture it will be explained why the speaker is a believer, and why some others are still sceptical.

We discuss combinatorial curvature on planar graphs and the consequences of negative curvature on the spectrum of the graph Laplacian. A particular focus lies on uniformly decreasing curvature. This case is characterized by purely discrete spectrum for which we present eigenvalue asymptotics, exponential decay of eigenfunctions and absence of compactly supported eigenfunctions. (The results include joint work with Michel Bonnefont, Sylvain Golenia, Norbert Peyerimhoff and Daniel Lenz).

We give some applications of intrinsic metrics to problems which arise on infinite graphs in the case of unbounded geometry. One is to the issue of essential self-adjointness, another is to estimate the bottom of the spectrum in terms of isoperimetric constants and volume growth.

A framework $(G,p)$ is the combination of a finite graph $G=(V,E)$ and a map $p:V\rightarrow \mathbb{R}^d$. $(G,p)$ is rigid if there is no edge-length preserving continuous motion of the vertices that does not arise as an isometry. For generic frameworks in the plane there is an efficient combinatorial description of rigidity due to Laman. This has recently been extended in two ways of interest to this talk. Firstly, a number of authors have considered frameworks in the plane that satisfy some symmetry but are otherwise as generic as possible. Secondly, Laman type theorems have been obtained for frameworks in $\mathbb{R}^3$ supported on surfaces.

In this talk I will discuss the rigidity of forced-symmetric frameworks on surfaces; that is, when there are no symmetry preserving motions of the vertices. In particular, I will describe necessary combinatorial conditions for a framework $(G,p)$ in $\mathbb{R}^3$ restricted to a fixed 2-dimensional irreducible algebraic variety $\mathcal{M}$, admitting a finite symmetry group $S\subset O(\mathbb{R}^3)$, to be rigid in terms of a voltage graph $(G,S)$. In the cases when $\mathcal{M}$ is a cylinder or a cone we discuss several special cases where it is possible to show these necessary conditions are also sufficient.

This is joint work with Bernd Schulze.

In this talk, I will present some connections (more or less recent) between the eigenvalues of a graph and its structure. I will focus on some connectivity problems in the theory of strongly regular and distance-regular graphs, connections between the second largest eigenvalue and the maximum number of edge-disjoint spanning trees of a regular graph and the problem of decomposing complete (hyper)graphs into the minimum number of (hyper)bicliques.

19:00 Wine

19:30 Dinner

In the first part of the talk, we study Platonic graphs, a family of regular graphs arising as quotients of the Farey tessellation by principal congruence subgroups G(N) of the modular group. For primes $N>3$, we use the wheel structure (Lanphier & Rosenhouse, 2004) of the Platonic graphs to show that they are $N$-vertex-connected, and next, we give a completely elementary proof of the theorem in (Gunnells, 2005) without number theory that each graph has exactly four distinct eigenvalues $1, 1/\sqrt(N), -1/N, -1/\sqrt(N)$ and thus, they are Ramanujan.

In the second part of the talk, we introduce a new family of highly regular trivalent expanders, tessellating compact hyperbolic surfaces. We show that the intersection of this family of trivalent expanders and the family of Platonic graphs is the single Platonic graph corresponding to $N=8$.

This is joint work with Norbert Peyerimhoff and Alina Vdovina.

The energy of a graph is the sum of the absolute values of the eigenvalues of the adjacency matrix (this concept was introduced by Gutman in 1978; it is related to the energy of a molecule). An important problem is to find graphs with $n$ vertices having maximal energy. Koolen and Moulton derived an upper bound and showed that it is tight if and only if the graph is strongly regular with specified parameters. These graphs are related to certain regular Hadamard matrices which lead to the existence of many graphs with maximum energy. Recently, some variations on this theme have been considered. This concerns the energy with respect to the Seidel adjacency matrix, and the energy per vertex of a regular graph. It turns out that the energy attains its maximum for symmetric conference matrices, and incidence graphs of projective planes, respectively. Results about the density of the mentioned combinatorial objects lead to asymptotic results for the various kinds of maximal energy.

The eigenvalues of the adjacency matrix of a graph contain a lot -- but not always all -- information on the structure of the graph. In this talk, we will dive deeper into graphs that have a lot of combinatorial symmetry: distance-regular graphs (such as Hamming graphs and Johnson graphs). We will give an overview of when distance-regularity is determined by the eigenvalues (and when it is not). We will see how systems of orthogonal polynomials can help to recognize distance-regular graphs from their eigenvalues and a little extra information through the `spectral excess theorem'. We then discuss how these methods and ideas led to the construction of the twisted Grassmann graphs, a family of distance-regular graphs that have the same spectrum as certain Grassmann graphs. These twisted graphs are currently the only known family of distance-regular graphs with unbounded diameter that are not vertex-transitive. If time permits, we also present a characterization of the generalized odd graphs ('the odd-girth theorem'), and discuss some results on graphs that are `almost distance-regular', in particular how the latter can be used to construct non-isomorphic graphs with the same eigenvalues.

A conjecture of Thomassen from 1982 states that for every $k$ there is an $f(k)$ such that every strongly $f(k)$-connected tournament contains k edge-disjoint Hamilton cycles. A classical theorem of Camion, that every strongly connected tournament contains a Hamilton cycle, implies that $f(1) = 1$. Until now, even the existence of $f(2)$ was open. In this talk, I will discuss a proof of Thomassen’s conjecture. Our methods in fact allow us to show that $f(k) = O(k^2 log^2 k)$, which is best possible up to the logarithmic factor. This is joint work with Daniela Kühn, John Lapinskas, and Deryk Osthus.

An arrangement of pseudocircles is a finite collection of Jordan curves in the plane with the additional properties that (i) no three of the curves meet in a point; (ii) every two curves meet in at most two points; and (iii) if two curves meet in a point $p$, then they cross at $p$.

We say that two arrangements $C = (c_1,..., c_n)$ and $D = (d_1,..., d_n)$ are equivalent if there is a homeomorphism $\phi$ of the plane onto itself such that $\phi[c_i] = d_i$ for all $i=1,...,n$. Linhart and Ortner (2005) gave an example of an arrangement of five pseudocircles that is not equivalent to an arrangement of circles, and conjectured that every arrangement of at most four pseudocircles is equivalent to an arrangement of circles. We prove their conjecture.

We consider two related recognition problems. The first is the problem of deciding, given a pseudocircle arrangement, whether it is equivalent to an arrangement of circles. The second is deciding, given a pseudocircle arrangement, whether it is equivalent to an arrangement of convex pseudocircles. We prove that both problems are NP-hard, answering questions of Bultena, Grünbaum and Ruskey (1998) and of Linhart and Ortner (2008).

We also give an example of a collection of convex pseudocircles with the property that its intersection graph (i.e. the graph with one vertex for each pseudocircle and an edge between two vertices if and only if the corresponding pseudocircles intersect) cannot be realized as the intersection graph of a collection of circles. This disproves a folklore conjecture communicated to us by Pyatkin.

Joint work with Tobias Müller.

Approximate Schedule:

Depart from Grey College 9.00 a.m. (packed lunches available)

Arrive Alnwick Castle and Gardens 10.30 a.m.

Lunch 12.00 p.m.

Depart for Durham 4.00 p.m.

Arrive Grey College 5.30 p.m.

In a series of the three talks, we present basic notions related to graph limits both in the dense and in the sparse sense and to permutation limits. We discuss their relation to property testing algorithms and quasirandomness as well as we overview applications in extremal combinatorics, in particular, the framework of flag algebras.

The basis graph of a matroid $M$ is the graph $G(M)$ whose vertices are the bases of $M$ and edges are the pairs $A,B$ of bases differing by a single exchange (i.e., $|A\Delta B| = 2$). Basis graphs of matroids have been characterized by Stephen Maurer (Matroid basis graphs I, J. Combin.Th. B 14, 1973, 216-240) as graphs satisfying two local conditions and a global metric condition. In his paper, Maurer conjectured that one can replace his global metric condition by the topological one requiring simply connectivity of the associated triangle-square complex (the triangle-square complex of a graph $G$ is a 2-dimensional complex in which the 2-cells are the triangles and the squares of $G$). Although since 1977 it was known to it be false in its original form, we show that the conjecture is true if we strengthen the local conditions. (Joint work with Jeremie Chalopin (LIF, Aix-Marseille Université) and Damian Osajda (Universtät Wien and Universytet Wroclawski), http://arxiv.org/pdf/1212.6879v1.pdf)

This will be a survey of methods developed in the last few years to prove results on growth in non-commutative groups. These techniques have their roots in both additive combinatorics and group theory, among other fields.

Testing a property P of graphs in the bounded-degree model deals with the following problem: given a graph $G$ of bounded degree $d$ we should distinguish (with probability $2/3$ , say) between the case that $G$ satises P and the case that one should add/remove at least $\epsilon dn$ edges of $G$ to make it satisfy P. In sharp contrast to property testing for dense graphs, which is relatively well understood, only few properties are known to be testable with a constant number of queries in the bounded-degree model.

We identify for the first time a natural family of global monotone property that can have an expander graph, which can be efficiently tested in the bounded degree model. Specically, we show that, for any integer $t$, $Kt$-subdivision-freeness is testable with a constant number of queries in the bounded-degree model. This property was not previously known to be testable even with $o(n)$ queries. Note that an expander graph with all degree less than $t-1$ does not have a $Kt$-subdivision. This generalizes the result by Itai Benjamini, Oded Schramm and Asaf Shapira (STOC'08 & Adv. Math 2010).

The proof is based on a novel combination of some results that develop the framework of partitioning oracles, together with structural graph theory results that develop the seminal graph minor theory by Robertson and Seymour.

Joint Work with Yuichi Yoshida (NII). To appear in STOC'13.

We prove the following results (via a unified approach) for all sufficiently large $n$:

(i) [1-factorization conjecture] Suppose that n is even and $D \ge n/2$. Then every $D$-regular graph $G$ on $n$ vertices has a decomposition into perfect matchings. Equivalently, the edge-chromatic number of $G$ is $D$.

(ii) [Hamilton decomposition conjecture] Suppose that $D \ge (n-1)/2$. Then every $D$-regular graph $G$ on $n$ vertices has a decomposition into Hamilton cycles and at most one perfect matching.

(iii) [Optimal packings of Hamilton cycles] Suppose that $G$ is a graph on $n$ vertices with minimum degree at least $n/2$. Then $G$ contains at least $(n-2)/8$ edge-disjoint Hamilton cycles.

According to Dirac, (i) was first raised in the 1950's. (ii) and (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible.

This is joint work with Bela Csaba (Szeged), Daniela Kuhn (Birmingham), Deryk Osthus (Birmingham) and Andrew Treglown (QMUL).

Median eigenvalues of a graph are closely related to the HOMO-LUMO separation properties from mathematical chemistry. The talk will give an overview of recent results about the median eigenvalues. One particular surprising discovery is that the median eigenvalues of every connected bipartite graph G of maximum degree at most three belong to the interval $[-1,1]$ with a single exception of the Heawood graph, whose median eigenvalues are $\pm\sqrt{2}$. Moreover, if $G$ is not isomorphic to the Heawood graph, then a positive fraction of its median eigenvalues lie in the interval $[-1,1]$.

In a series of the three talks, we present basic notions related to graph limits both in the dense and in the sparse sense and to permutation limits. We discuss their relation to property testing algorithms and quasirandomness as well as we overview applications in extremal combinatorics, in particular, the framework of flag algebras.

An incidentor in a directed loopless multigraph $G=(V,E)$ is an ordered pair $(v,e)$, where $v \in V,$ $e \in E$ and the vertex $v$ is incident with the arc $e$. It is convenient to treat an incidentor $(v,e)$ as a half of the arc $e$, adjoining to the vertex $v$. Two incidentors $(v,e_1)$ and $(v,e_2)$, adjoining to the same vertex $v$ are called adjacent. For an arc $e=uv$ the incidentor $(u,e)$ is initial and the incidentor $(v,e)$ is final. The initial and the final incidentors of the same arc are called mated. Denote by $I$ the set of all incidentors of the graph. Then an incidentor coloring is an arbitrary function $f:I \to {\mathbb Z}_+$, where ${\mathbb Z}_+$ is the set of positive integers or colors. Setting restrictions on the colors of adjacent and mated incidentors one can obtain a rich class of incidentor coloring problems. In particular, this class includes both edge and vertex coloring problems. The first incidentor coloring problem arose in [1] as a model for an information transmission problem in a local network. In the talk various types of the incidentor colorings will be considered and a review of known methods and results will be given. The work was supported by Russian Foundation for Basic Research (project 12-01-33028).

References

[1] A.V. Pyatkin: Some optimization problems of scheduling the transmission of messages in a local communication network, Discr. anal. and oper. research. 1995. V. 2. N.4. P. 74–-79 (in Russian). Translation: A.V. Pyatkin: Some optimization problems of scheduling the transmission of messages in a local communication network, A. D. Korshunov (ed.), Operations Research and Discrete Analysis. Netherlands: Kluwer Academic Publishers. 1997. P. 227–-232.

The Tutte polynomial of a graph $G$ is a two variable polynomial $T(G;x,y)$, which encodes much information about $G$. The number of spanning trees in $G$, the number of acyclic orientations of $G$, and the partition function of the $q$-state Potts model are all specialisations of the Tutte polynomial. Jackson and Sokal have studied the sign of the Tutte polynomial, and identified regions in the $(x,y)$-plane where it is ``essentially determined'', in the sense that the sign is a function of very simple characteristics of $G$, e.g., the number of vertices and connected components of $G$. It is natural to ask whether the sign of the Tutte polynomial is hard to compute outside of the regions where it is essentially determined. We show that the answer to this question is often an emphatic ``yes'': specifically, that determining the sign is #P-hard. In such cases, approximating the Tutte polynomial with small relative error is also #P hard, since in particular the sign must be determined. In the other direction, we can ask whether the Tutte polynomial is easy to approximate in regions where the sign is essentially determined. The answer is not straightforward, but there is evidence that it often ``no''.

This is joint work with Leslie Ann Goldberg (Oxford).

The Poincaré upper half plane has been of interest to artists, complex analysts, geometers, number theorists, and physicists for many reasons. It is just the ordinary upper half plane with a new Poincaré distance (using $(x,y)$ coordinates, the Euclidean arc length differential squared being $ds^2=dx^2+dy^2$ and the Poincaré $ds^2$ being the Euclidean one divided by $y^2$). In the Poincaré case, Euclid's 5th postulate fails. But the geometry is still a perfectly reasonable one. Escher's circle limit pictures give a taste of that how that geometry looks to the Euclidean eye. Wiles proof of the Fermat conjecture shows the importance for number theory of the functions that live on this space and are have a periodicity property under fractional linear transformation by the modular group of $2 \times 2$ matrices with integer entries and determinant 1. These functions are called "modular forms."

In the first part of this talk, I will summarize the basics about the Poincaré upper half plane and modular forms. Then I will consider what happens if you replace the field of real numbers with a finite field. Analogs of the Poincaré Laplacian are the adjacency operators of finite upper half plane graphs. It turns out that the graphs are Ramanujan and there are interesting finite analogs of modular forms for analogs of the modular group in this context.

The classical randomized rumour spreading protocol has been introduced and first investigated by Frieze and Grimmett (1985). Initially, one vertex of a finite, undirected and connected graph has some piece of information (“rumour”). In each round, every one of the informed vertices chooses one of its neighbours uniformly and independently at random and informs it. I will talk about the performance and robustness of this protocol on random graphs, and I will also consider a quasirandom version of the rumour spreading protocol, proposed by Doerr, Friedrich, and Sauerwald (2008). This is joint work with Benjamin Doerr, Spyros Angelopoulos, Nikolaos Fountoulakis, Ariel Levavi, and Konstantinos Panagiotou.

In a series of papers, Audrey Terras and I introduced zeta functions of graphs with multiple variables. By specializing these variables in various ways, we recover other zeta functions previously defined. For example, setting all the variables to be a single common variable, we recover the Ihara zeta function of a graph. Other possibilities will be discussed in the talk.

In a series of the three talks, we present basic notions related to graph limits both in the dense and in the sparse sense and to permutation limits. We discuss their relation to property testing algorithms and quasirandomness as well as we overview applications in extremal combinatorics, in particular, the framework of flag algebras.

The Perron-Frobenius is a particularly useful basic result in the study of positive matrices, with useful applications to graphs. A natural infinite dimensional analogue of this is the Ruelle Operator Theorem. Recently, there has been considerable interest in non-linear (fixed point) versions of the Perron-Frobenius theorem. We will discuss a particular non-linear version of the Ruelle Operator Theorem.

Network coding is a novel means to transmit data through a network. The problem of network coding solvability is simple in essence: given a network, a set of sources which transmit messages to a set of destinations across that network, can all the messages be effectively transmitted? This problem is hard in practice, and the entropy of a digraph was introduced by Riis as a means to determine whether an instance of network coding is solvable. Recently, a closure operator on all subsets of vertices of a digraph was introduced, thus reducing the entropy of the digraph to a problem on its closure. We then show how to apply results on closure operators in general to obtain results on the digraph entropy, and especially on network coding solvability.

Random intersection graphs are characterize by three parameters: $n$, $m$ and $p$, where $n$ is the number of vertices, $m$ is a set of objects, and $p$ is the probability that a given object is associated with a given vertex. Two vertices in a random intersection graph are adjacent if and only if they have an associated object in common. When $m=\lfloor n^\alpha\rfloor$ for constant $\alpha$, we provide a condition, called strictly $\alpha$-balanced, for the Poisson convergence for the number of induced copies of a fixed subgraph. This is joint work with Katarzyna Rybarczyk-Krzywdzinska.

Recently there was a considerable amount of interest in computing spectral properties of random walk operators (and more generally - group ring operators) on Cayley graphs of lamplighter-type groups. In all cases such computations require some non-trivial input from combinatorics. For example, Lehner and Wagner computed the kernel dimension of a random walk operator on the free lamplighter group by being able to explicitly write down the generating function for the size of the maximal matching in finite trees. In the talk I will explain how the relation between the spectrum of the random walk and combinatorics is usually established. I'll start with briefly surveying some of the success stories of this technique and if time permits I'll mention two elementary combinatorial problems whose solutions would give some new information about random walk operators. One is related to the generating functions of languages in the complexity class LOGSPACE, and the other is related to coefficients of noncommutative rational functions whose coefficients are powers of a fixed prime number.

We consider a few NP-hard graph problems arising in context of biological and social network analysis. Motivated by the (worst-case) intractability of these practically relevant computational problems, we discuss some algorithmic results exploiting multivariate parameterizations of the problems. We also attempt to link our findings to a better understanding of corresponding heuristic algorithms.