Past Combinatorial Theory Seminar

In an Erdős--R\'enyi random graph above the phase transition, i.e.,

where there is a giant component, the size of (number of vertices in)

this giant component is asymptotically normally distributed, in that

its centred and scaled size converges to a normal distribution. This

statement does not tell us much about the probability of the giant

component having exactly a certain size. In joint work with B\'ela

Bollob\'as we prove a `local limit theorem' answering this question

for hypergraphs; the graph case was settled by Luczak and Łuczak.

The proof is based on a `smoothing' technique, deducing the local

limit result from the (much easier) `global' central limit theorem.

Results that say local information is enough to guarantee global information provide the theoretical underpinnings of many reconstruction algorithms in evolutionary biology. Such results include Buneman's Splits-Equivalence Theorem and the Tree-Metric Theorem. The first result says that, for a collection $\mathcal C$ of binary characters, pairwise compatibility is enough to guarantee compatibility for $\mathcal C$, that is, there is a phylogenetic (evolutionary) tree that realises $\mathcal C$. The second result says that, for a distance matrix $D$, if every $4\times 4$ distance submatrix of $D$ is realisable by an edge-weighted phylogenetic tree, then $D$ itself is realisable by such a tree. In this talk, we investigate these and other results of this type. Furthermore, we explore the closely-related task of determining how much information is enough to reconstruct the correct phylogenetic tree.

We study the problem of covering R^d by overlapping translates of a convex polytope, such that almost every point of R^d is covered exactly k times. Such a covering of Euclidean space by a discrete set of translations is called a k-tiling. The investigation of simple tilings by translations (which we call 1-tilings in this context) began with the work of Fedorov and Minkowski, and was later extended by Venkov and McMullen to give a complete characterization of all convex objects that 1-tile R^d. By contrast, for k ≥ 2, the collection of polytopes that k-tile is much wider than the collection of polytopes that 1-tile, and there is currently no known analogous characterization for the polytopes that k-tile. Here we first give the necessary conditions for polytopes P that k-tile, by proving that if P k-tiles R^d by translations, then it is centrally symmetric, and its facets are also centrally symmetric. These are the analogues of Minkowski’s conditions for 1-tiling polytopes, but it turns out that very new methods are necessary for the development of the theory. In the case that P has rational vertices, we also prove that the converse is true; that is, if P is a rational, centrally symmetric polytope, and if P has centrally symmetric facets, then P must k-tile R^d for some positive integer k.

We call a graph $H$ \emph{Ramsey-unsaturated} if there is an edge in the

complement of $H$ such that the Ramsey number $r(H)$ of $H$ does not

change upon adding it to $H$. This notion was introduced by Balister,

Lehel and Schelp who also showed that cycles (except for $C_4$) are

Ramsey-unsaturated, and conjectured that, moreover, one may add {\em

any} chord without changing the Ramsey number of the cycle $C_n$, unless

$n$ is even and adding the chord creates an odd cycle.

We prove this conjecture for large cycles by showing a stronger

statement: If a graph $H$ is obtained by adding a linear number of

chords to a cycle $C_n$, then $r(H)=r(C_n)$, as long as the maximum

degree of $H$ is bounded, $H$ is either bipartite (for even $n$) or

almost bipartite (for odd $n$), and $n$ is large.

This motivates us to call cycles \emph{strongly} Ramsey-unsaturated.

Our proof uses the regularity method.

Graphs and digraphs behave quite differently, and many classical results for graphs are often trivially false when extended to general digraphs. Therefore it is usually necessary to restrict to a smaller family of digraphs to obtain meaningful results. One such very natural family is Eulerian digraphs, in which the in-degree equals out-degree at every vertex.

In this talk, we discuss several natural parameters for Eulerian digraphs and study their connections. In particular, we show that for any Eulerian digraph G with n vertices and m arcs, the minimum feedback arc set (the smallest set of arcs whose removal makes G acyclic) has size at least $m^2/2n^2+m/2n$, and this bound is tight. Using this result, we show how to find subgraphs of high minimum degrees, and also long cycles in Eulerian digraphs. These results were motivated by a conjecture of Bollob\'as and Scott.

Joint work with Ma, Shapira, Sudakov and Yuster

It is very well known that every graph on $n$ vertices and $m$ edges admits a bipartition of size at least $m/2$. This bound can be improved to $m/2 + (n-1)/4$ for connected graphs, and $m/2 + n/6$ for graphs without isolated vertices, as proved by Edwards, and Erd\"os, Gy\'arf\'as, and Kohayakawa, respectively. A bisection of a graph is a bipartition in which the size of the two parts differ by at most 1. We prove that graphs with maximum degree $o(n)$ in fact admit a bisection which asymptotically achieves the above bounds.These results follow from a more general theorem, which can also be used to answer several questions and conjectures of Bollob\'as and Scott on judicious bisections of graphs.
Joint work with Po-Shen Loh and Benny Sudakov

Random geometric graphs have been well studied over the last 50 years or so. These are graphs that

are formed between points randomly allocated on a Euclidean space and any two of them are joined if

they are close enough. However, all this theory has been developed when the underlying space is

equipped with the Euclidean metric. But, what if the underlying space is curved?

The aim of this talk is to initiate the study of such random graphs and lead to the development of

their theory. Our focus will be on the case where the underlying space is a hyperbolic space. We

will discuss some typical structural features of these random graphs as well as some applications,

related to their potential as a model for networks that emerge in social life or in biological

sciences.

We discuss some recent developments on the following long-standing problem known as Ryser's

conjecture. Let $H$ be an $r$-partite $r$-uniform hypergraph. A matching in $H$ is a set of disjoint

edges, and we denote by $\nu(H)$ the maximum size of a matching in $H$. A cover of $H$ is a set of

vertices that intersects every edge of $H$. It is clear that there exists a cover of $H$ of size at

most $r\nu(H)$, but it is conjectured that there is always a cover of size at most $(r-1)\nu(H)$.

Rado introduced the following `lion and man' game in the 1930's: two players (the lion and the man) are in the closed unit disc and they can run at the same speed. The lion would like to catch the man and the man would like to avoid being captured.

This game has a chequered history with several false `winning strategies' before Besicovitch finally gave a genuine winning strategy.

We ask the surprising question: can both players win?

A dot product representation of a graph assigns to each vertex $s$ a vector $v(s)$ in ${\bf R}^k$ in such a way that $v(s)^T v(t)$ is greater than $1$ if and only $st$ is an edge. Similarly, in a distance representation $|v(s)-v(t)|$ is less than $1$ if and only if $st$ is an edge.

I will discuss the solution of some open problems by Spinrad, Breu and Kirkpatrick and others on these and related geometric representations of graphs. The proofs make use of a connection to oriented pseudoline arrangements.

(Joint work with Colin McDiarmid and Ross Kang)

If $A$ is a set of $n$ positive integers, how small can the set

$\{ x/(x,y) : x,y \in A \}$ be? Here, as usual, $(x,y)$ denotes the highest common factor of

$x$ and $y$. This elegant question was raised by Granville and Roesler, who

also reformulated it in the following way: given a set $A$ of $n$ points in

the integer grid ${\bf Z}^d$, how small can $(A-A)^+$, the projection of the difference

set of $A$ onto the positive orthant, be?

Freiman and Lev gave an example to show that (in any dimension) the size can

be as small as $n^{2/3}$ (up to a constant factor). Granville and Roesler

proved that in two dimensions this bound is correct, i.e. that the size is

always at least $n^{2/3}$, and they asked if this holds in any dimension.

After some background material, the talk will focus on recent developments.

Joint work with B\'ela Bollob\'as.

In Achlioptas processes, starting from an empty graph, in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. Although the evolution of such `local' modifications of the Erdös-Rényi random graph processes has received considerable attention during the last decade, so far only rather `simple' rules are well-understood. Indeed, the main focus has been on bounded size rules (where all component sizes larger than some constant B are treated the same way), and for more complex rules hardly any rigorous results are known. In this talk we will discuss a new approach that applies to many involved Achlioptas processes: it allows us to prove that certain key statistics are tightly concentrated during the early evolution of e.g. the sum and product rule.

Joint work with Oliver Riordan.

The phase transition deals with sudden global changes and is observed in many fundamental random discrete structures arising from statistical physics, mathematics and theoretical computer science, for example, Potts models, random graphs and random $k$-SAT. The phase transition in random graphs refers to the phenomenon that there is a critical edge density, to which adding a small amount results in a drastic change of the size and structure of the largest component. In the Erdős--R\'enyi random graph process, which begins with an empty graph on $n$ vertices and edges are added randomly one at a time to a graph, a phase transition takes place when the number of edges reaches $n/2$ and a giant component emerges. Since this seminal work of Erdős and R\'enyi, various random graph processes have been introduced and studied. In this talk we will discuss new approaches to study the size and structure of components near the critical point of random graph processes: key techniques are the classical ordinary differential equations method, a quasi-linear partial differential equation that tracks key statistics of the process, and singularity analysis.

We shall discuss how the algebra norm can be used to identify structure in groups. No prior familiarity with the area will be assumed.

We say that a hypergraph is \emph{stable} if each sufficiently large subset of its vertices either spans many hyperedges or is very structured. Hypergraphs that arise naturally in many classical settings posses the above property. For example, the famous stability theorem of Erdos and Simonovits and the triangle removal lemma of Ruzsa and Szemeredi imply that the hypergraph on the vertex set $E(K_n)$ whose hyperedges are the edge sets of all triangles in $K_n$ is stable. In the talk, we will present the following general theorem: If $(H_n)_n$ is a sequence of stable hypergraphs satisfying certain technical conditions, then a typical (i.e., uniform random) $m$-element independent set of $H_n$ is very structured, provided that $m$ is sufficiently large. The above abstract theorem has many interesting corollaries, some of which we will discuss. Among other things, it implies sharp bounds on the number of sum-free sets in a large class of finite Abelian groups and gives an alternate proof of Szemeredi’s theorem on arithmetic progressions in random subsets of integers.

Joint work with Noga Alon, Jozsef Balogh, and Robert Morris.

An embedding of a graph H in a graph G is an injective mapping of the vertices of H to the vertices of G such that edges of H are mapped to edges of G. Embedding problems have been extensively studied. A very powerful tool in this area is Szemeredi's Regularity Temma. It approximates the host graph G by a quasirandom graph which inherits many of the properties of G. Unfortunately the direct use of Szemeredi's Regularity Lemma is useless if the host graph G is sparse.

During the talk I shall expose a technique to deal with embedding trees in sparse graphs. This technique has been developed by Ajtai, Komlos,Simonovits and Szemeredi to solve the Erdos-Sos conjecture. Presently the author together with Hladky, Komlos, Simonovits, Stein and Szemeredi apply this method to solve the related conjecture of Loebl, Komlos and Sos (approximate version).

Hex was discovered independently by Piet Hein in Copenhagen in 1942 and byJohn Nash in Princeton in 1948.  The game is interesting because its rules are very simple, yet it is not known how to play best possible.  For example, a winning first move for the first player (who does have  a winning strategy) is still unknown. The talk will tell the history of the game and give simple proofs for basic results about it. Also the reverse game of HEX,sometimes called REX, will be discussed. New results about REX are under publication in Discrete Mathematics in a paper:  How to play Reverse Hex (joint work with Ryan Hayward and Phillip Henderson).

The induced graph removal lemma states that for any fixed graph $H$ on $h$ vertices and any $e\textgreater 0$ there exists $d\textgreater0$ such that any graph $G$ with at most $d n^h$ induced copies of $H$ may be made $H$-free by adding or removing atmost $e n^2$ edges. This fact was originally proven by Alon, Fischer, Krivelevich and Szegedy. In this talk, we discuss a new proof and itsrelation to various regularity lemmas. This is joint work with Jacob Fox.

It is known that generic and universal structures and Ramsey classes are related. We explain this connection and complement it by some new examples. Particularly we disscuss universal and Ramsey classes defined by existence and non-existence of homomorphisms.

The 2-dimensional assignment problem (minimum cost matching) is solvable in polynomial time, and it is known that a random instance of size n, with entries chosen independently and uniformly at random from [0,1], has expected cost tending to π^2/6.  In dimensions 3 and higher, the "planar" assignment problem is NP-complete, but what is the expected cost for a random instance, and how well can a heuristic do?  In d dimensions, the expected cost is of order at least n^{2-d} and at most ln n times larger, but the upper bound is non-constructive.  For 3 dimensions, we show a heuristic capable of producing a solution within a factor n^ε of the lower bound, for any constant ε, in time of order roughly n^{1/ε}.  In dimensions 4 and higher, the question is wide open: we don't know any reasonable average-case assignment heuristic.

We consider random walks on two classes of random graphs and explore the likely structure of the the set of unvisited vertices or vacant set. In both cases, the size of the vacant set $N(t)$ can be obtained explicitly as a function of $t$. Let $\Gamma(t)$ be the subgraph induced by the vacant set. We show that, for random graphs $G_{n,p}$ above the connectivity threshold, and for random regular graphs $G_r$, for constant $r\geq 3$, there is a phase transition in the sense of the well-known Erdos-Renyi phase transition. Thus for $t\leq (1-\epsilon)t^*$ we have a unique giant plus components of  size $O(\log n)$ and for $t\geq (1+\epsilon)t^*$ we have only components of  size $O(\log n)$.

In the case of $G_r$ we describe the likely degree sequence, size of the giant component and structure of the small ($O(\log n)$) size components.

A random planar graph $P_n$ is a graph drawn uniformly at random from the class of all (labelled) planar graphs on $n$ vertices. In this talk we show that with probability $1-o(1)$ the number of vertices of degree $k$ in $P_n$ is very close to a quantity $d_k n$ that we determine explicitly. Here $k=k(n) \le c \log n$. In the talk our main emphasis will be on the techniques for proving such results. (Joint work with Kosta Panagiotou.)

We highlight a technique for studying edge colourings of multigraphs, due to Tashkinov. This method is a sophisticated generalisation of the method of alternating paths, and builds upon earlier work by Kierstead and Goldberg. In particular we show how to apply it to a number of edge colouring problems, including the question of whether the class of multigraphs that attain equality in Vizing's classical bound can be characterised.

This talk represents joint work with Jessica McDonald.

In 1961 Hajos conjectured that if a graph contains no subdivsion of a clique of order t then its chromatic number is less than t. In 1981, Erdos and Fajtlowicz showed that the conjecture is almost always false. We show it is almost always true. This is joint work with Keevash, Mohar, and McDiarmid.

I shall describe some recent results about the asymptotic behaviour of matroids.

Specifically almost all matroids are simple and have probability at least 1/2 of being connected.

Also, various quantitative results about rank, number of bases and number and size of circuits of almost all matroids are given. There are many open problems and I shall not assume any previous knowledge of matroids. This is joint work, see below.

1 D. Mayhew, M. Newman, D. Welsh and G. Whittle,

On the asymptotic properties of connected matroids, European J. Combin. to appear

2 J. Oxley, C. Semple, L. Wasrshauer and D. Welsh,

On properties of almost all matroids, (2011) submitted

The $C_\ell$-free process starts with the empty graph on $n$ vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of $C_\ell$ is created. For every $\ell \geq 4$ we show that, with high probability as $n \to \infty$, the maximum degree is $O((n \log n)^{1/(\ell-1)})$, which confirms a conjecture of Bohman and Keevash and improves on bounds of Osthus and Taraz. Combined with previous results this implies that the $C_\ell$-free process typically terminates with $\Theta(n^{\ell/(\ell-1)}(\log n)^{1/(\ell-1)})$ edges, which answers a question of Erd\H{o}s, Suen and Winkler. This is the first result that determines the final number of edges of the more general $H$-free process for a non-trivial \emph{class} of graphs $H$. We also verify a conjecture of Osthus and Taraz concerning the average degree, and obtain a new lower bound on the independence number. Our proof combines the differential equation method with a tool that might be of independent interest: we establish a rigorous way to `transfer' certain decreasing properties from the binomial random graph to the $H$-free process.

How many triangles must a graph of density d contain? This old question due to Erdos was recently answered by Razborov, after many decades of progress by numerous authors.

We will consider the analogous question for tripartite graphs. Given a tripartite graph with prescribed edges densities between each

pair of classes how many triangles must it contain?

A family of graphs F on a fixed set of n vertices is said to be triangle-intersecting if for any two graphs G,H in F, the intersection of G and H contains a triangle. Simonovits and Sos conjectured that such a family has size at most (1/8)2^{\binom{n}{2}}, and that equality holds only if F
consists of all graphs containing some fixed triangle. Recently, the author, Yuval Filmus and Ehud Friedgut proved a strengthening of this conjecture, namely that if F is an odd-cycle-intersecting family of graphs, then |F| \leq (1/8) 2^{\binom{n}{2}}. Equality holds only if F consists of all graphs containing some fixed triangle. A stability result also holds: an odd-cycle-intersecting family with size close to the maximum must be close to a family of the above form. We will outline proofs of these results, which use Fourier analysis, together with an analysis of the properties of random cuts in graphs, and some results in the theory of Boolean functions. We will then discuss some related open questions.

All will be based on joint work with Yuval Filmus (University of Toronto) and Ehud Friedgut (Hebrew University of Jerusalem).

Combinatorial pattern matching is a subject which has given us fast and elegant algorithms for a number of practical real world problems as well as being of great theoretical interest. However, when single character wildcards or so-called "don't know" symbols are introduced into the input, classic methods break down and it becomes much more challenging to find provably fast solutions. This talk will give a brief overview of recent results in the area of pattern matching with don't knows and show how techniques from fields as disperse FFTs, group testing and algebraic coding theory have been required to make any progress. We will, if time permits, also discuss the main open problems in the area.

We revisit the problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time sorting algorithm achieving this bound up to a constant factor. They established a crucial link between the entropy of the input partial order and the information-theoretic lower bound. However, their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it unpractical. We develop efficient algorithms for sorting under partial information, derived from approximation and exact algorithms for computing the partial order entropy.

This is joint work with S. Fiorini, G. Joret, R. Jungers, and I. Munro.

The problem of checking existence for an Euler tour of a graph is trivial (are all vertex degrees even?). The problem of counting (or even approximate counting) Euler tours seems to be very difficult. I will describe two simple classes of graphs where the problem can be

solved exactly in polynomial time. And also talk about the many many classes of graphs where no positive results are known.

Consider a configuration of points in $d$-dimensional Euclidean space

together with a set of constraints

which fix the direction or the distance between some pairs of points.

Basic questions are whether the constraints imply that the configuration

is unique or locally unique up to congruence, and whether it is bounded. I

will describe some solutions

and partial solutions to these questions.

Whether as the sudoku puzzles of popular culture or as

restricted coloring problems on graphs or hypergraphs, completing partial

Latin squares and cubes present a framework for a variety of intriguing

problems. In this talk we will present several recent results on

completing partial Latin squares and cubes.

Suppose that $A \subset \mathbb F_2^n$ has density $\Omega(1)$. How

large a subspace is $A+A:=\{a+a’:a,a’ \in A\}$ guaranteed to contain? We

discuss this problem and how the the result changes as the density

approaches $1/2$.

In this talk we will first survey results which guarantee the existence of

spanning subgraphs in dense graphs. This will lead us to the proof of the

bandwidth-conjecture by Bollobas and Komlos, which states that any graph

with minimum degree at least $(1-1/r+\epsilon)n$ contains every r-chromatic graph

with bounded maximum degree and sublinear bandwidth as a spanning subgraph.

We will then move on to discuss the analogous question for a host graph that

is obtained by starting from a sparse random graph G(n,p) and deleting a

certain portion of the edges incident at every vertex.

This is joint work with J. Boettcher, Y. Kohayakawa and M. Schacht.

The Wulff droplet arises by conditioning a spin system in a dominant

phase to have an excess of signs of opposite type. These gather

together to form a droplet, with a macroscopic Wulff profile, a

solution to an isoperimetric problem.

I will discuss recent work proving that the phase boundary that

delimits the signs of opposite type has a characteristic scale, both

at the level of exponents and their logarithmic corrections.

This behaviour is expected to be shared by a broad class of stochastic

interface models in the Kardar-Parisi-Zhang class. Universal

distributions such as Tracy-Widom arise in this class, for example, as

the maximum behaviour of repulsive particle systems. time permitting,

I will explain how probabilistic resampling ideas employed in spin

systems may help to develop a qualitative understanding of the random

mechanisms at work in the KPZ class.

Given a graph we want to draw it in the plane; well we *want* to draw it in the plane, but sometimes we just can't. So we resort to various compromises. Sometimes we add crossings and try to minimize the crossings. Sometimes we add handles and try to minimize the number of handles. Sometimes we add crosscaps and try to minimize the number of crosscaps.

Sometimes we mix these parameters: add a given number of handles (or crosscaps) and try to minimize the number of crossings on that surface. What if we are willing to trade: say adding a handle to reduce the number of crossings? What can be said about the relative value of such a trade? Can we then add a second handle to get an even greater reduction in crossings? If so, why didn't we trade the second handle in the first place? What about a third handle?

The crossing sequence cr_1, cr_2, ... , cr_i, ... has terms the minimum number of crossings over all drawings of G on a sphere with i handles attached. The non-orientable crossing sequence is defined similarly. In this talk we discuss these crossing sequences.

By Dan Archdeacon, Paul Bonnington, Jozef Siran, and citing works of others.

We define the edge reconnecting model, a random multigraph evolving in time. At each time step we change one endpoint of a uniformly chosen edge: the new endpoint is chosen by linear preferential attachment. We consider a sequence of edge reconnecting models where the sequence of initial multigraphs is convergent in a sense which is a natural generalization of the Lovász-Szegedy notion of convergence of dense graph sequences. We investigate how the limit objects evolve under the edge reconnecting dynamics if we rescale time properly: we give the complete characterization of the time evolution of the limiting object from its initial state up to the stationary state using the theory of exchangeable arrays, the Pólya urn model, queuing and diffusion processes. The number of parallel edges and the degrees evolve on different timescales and because of this the model exhibits “aging”.

This talk considers the problem of sampling an independent set uniformly at random from a bipartite graph (equivalently, the problem of approximately counting independent sets in a bipartite graph). I will start by discussing some natural Markov chain approaches to this problem, and show why these lead to slow convergence. It turns out that the problem is interesting in terms of computational complexity – in fact, it turns out to be equivalent to a large number of other problems, for example, approximating the partition function of the “ferromagnetic Ising model’’ (a 2-state particle model from statistical physics) in the presence of external fields (which are essentially vertex weights). These problems are all complete with respect to approximation-preserving reductions for a logically-defined complexity class, which means that if they can be approximated efficiently, so can the entire class. In recent work, we show some connections between this class of problems and the problem of approximating the partition function of the ``ferromagnetic Potts model’’ which is a generalisation of the Ising model—our result holds for q>2 spins. (This corresponds to the approximation problem for the Tutte polynomial in the upper quadrant

above the hyperbola q=2.) That result was presented in detail at a recent talk given by Mark Jerrum at Oxford’s one-day meeting in combinatorics. So I will just give a brief description (telling you what the Potts model is and what the result is) and then conclude with some more recently discovered connections to counting graph homomorphisms and approximating the cycle index polynomial.

In the Max Acyclic Subdigraph problem we are given a digraph $D$ and ask whether $D$ contains an acyclic subdigraph with at least $k$ arcs. The problem is NP-complete and it is easy to see that the problem is fixed-parameter tractable, i.e., there is an algorithm of running time $f(k)n$ for solving the problem, where $f$ is a computable function of $k$ only and $n=|V(D)|$. The last result follows from the fact that the average number of arcs in an acyclic subdigraph of $D$ is $m/2$, where $m$ is the number of arcs in $D$. Thus, it is natural to ask another question: does $D$ have an acyclic subdigraph with at least $m/2 +k$ arcs?

Mahajan, Raman and Sikdar (2006, 2009), and by Benny Chor (prior to 2006) asked whether this and other problems parameterized above the average are fixed-parameter tractable (the problems include Max $r$-SAT, Betweenness, and Max Lin). Most of there problems have been recently shown to be fixed-parameter tractable.

Methods involved in proving these results include probabilistic inequalities, harmonic analysis of real-valued

functions with boolean domain, linear algebra, and algorithmic-combinatorial arguments. Some new results obtained in this research are of potential interest for several areas of discrete mathematics and computer science. The examples include a new variant of the hypercontractive inequality and an association of Fourier expansions of real-valued functions with boolean domain with weighted systems of linear equations over $F^n_2$.

I’ll mention results obtained together with N. Alon, R. Crowston, M. Jones, E.J. Kim, M. Mnich, I.Z. Ruzsa, S. Szeider, and A. Yeo.

A graph is $\chi$-bounded with a function $f$ is for all induced subgraph H of G, we have $\chi(H) \le f(\omega(H))$.  Here, $\chi(H)$ denotes the chromatic number of $H$, and $\omega(H)$ the size of a largest clique in $H$. We will survey several results saying that excluding various kinds of induced subgraphs implies $\chi$-boundedness. More precisely, let $L$ be a set of graphs. If a $C$ is the class of all graphs that do not any induced subgraph isomorphic to a member of $L$, is it true that there is a function $f$ that $\chi$-bounds all graphs from $C$? For some lists $L$, the answer is yes, for others, it is no.  

A decomposition theorems is a theorem saying that all graphs from a given class are either "basic" (very simple), or can be partitioned into parts with interesting relationship. We will discuss whether proving decomposition theorems is an efficient method to prove $\chi$-boundedness. 

The line graph operation, in which the edges of one graph are taken as the vertices of a new graph with adjacency preserved, is arguably the most interesting of graph transformations. In this survey, we will begin looking at characterisations of line graphs, focusing first on results related to our set of nine forbidden subgraphs. This will be followed by a discussion of some generalisations of line graphs, including our investigations into the Krausz dimension of a graph G, defined as the minimum, over all partitions of the edge-set of G into complete subgraphs, of the maximum number of subgraphs containing any vertex (the maximum in Krausz's characterisation of line graphs being 2).

The line graph operation, in which the edges of one graph are taken as the vertices of a new graph with adjacency preserved, is arguably the most interesting of graph transformations.  In this survey, we will begin looking at characterisations of line graphs, focusing first on results related to our set of nine forbidden subgraphs. This will be followed by a discussion of some generalisations of line graphs, including our investigations into the Krausz dimension of a graph G, defined as the minimum, over all partitions of the edge-set of G into complete subgraphs, of the maximum number of subgraphs containing any vertex (the maximum in Krausz's characterisation of line graphs being 2).