Tue, 23 Feb 2010
14:30
L3

Line Graphs and Beyond

Lowell Beineke
(Purdue)
Abstract

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

Tue, 23 Feb 2010

14:30 - 15:30
L3

Line Graphs and Beyond

Lowell Beineke
(Purdue)
Abstract

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

Thu, 18 Feb 2010
17:00
L3

Compact Apporximations and Topological Complexity of definable Sets

Nicolai Vorobjov
(Bath)
Abstract

We study upper bounds on topological complexity of sets definable in o-minimal structures over the reals. We suggest a new construction for approximating a large class of definable sets, including the sets defined by arbitrary Boolean combinations of equations and inequalities, by compact sets.

Those compact sets bound from above the homotopies and homologies of the approximated sets.

The construction is applicable to images under definable maps.

Based on this construction we refine the previously known upper bounds on Betti numbers of semialgebraic and semi-Pfaffian sets defined by quantifier-free formulae, and prove similar new upper bounds, individual for different Betti numbers, for their images under arbitrary continuous definable maps.

Joint work with A. Gabrielov.

Mon, 08 Mar 2010

12:00 - 13:00
L3

New approaches to problems posed by Sir Roger Penrose

George Sparling
(University of Pittsburgh)
Abstract

I will outline two areas currently under study by myself and my co-workers, particularly Jonathan Holland: one concerns the relation between the exceptional Lie group G_2 and Einstein's gravity; the second will introduce and apply the concept of a causal geometry.

Tue, 16 Feb 2010

15:45 - 16:45
L3

Moduli Spaces of Sheaves on Toric Varieties

Martijn Kool
(Oxford)
Abstract

Extending work of Klyachko, we give a combinatorial description of pure equivariant sheaves on a nonsingular projective toric variety X and use this description to construct moduli spaces of such sheaves. These moduli spaces are explicit and combinatorial in nature. Subsequently, we consider the moduli space M of all Gieseker stable sheaves on X and describe its fixed point locus in terms of the moduli spaces of pure equivariant sheaves on X. As an application, we compute generating functions of Euler characteristics of M in case X is a toric surface. In the torsion free case, one finds examples of new as well as known generating functions. In the pure dimension 1 case using a conjecture of Sheldon Katz, one obtains examples of genus zero Gopakumar-Vafa invariants of the canonical bundle of X.

Tue, 09 Mar 2010

14:30 - 15:30
L3

Establishing Complexity of Problems Parameterized Above Average

Gregory Z. Gutin
(Royal Holloway)
Abstract

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.

Tue, 02 Mar 2010

14:30 - 15:30
L3

Decomposition of graphs and $\chi$-boundedness

Nicolas Trotignon
(Paris)
Abstract

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. 

Tue, 16 Feb 2010

14:30 - 15:30
L3

Boundary properties of graphs

Vadim Lozin
(Warwick)
Abstract

The notion of a boundary graph property is a relaxation of that of a

minimal property. Several fundamental results in graph theory have been obtained in

terms of identifying minimal properties. For instance, Robertson and Seymour showed that

there is a unique minimal minor-closed property with unbounded tree-width (the planar

graphs), while Balogh, Bollobás and Weinreich identified nine minimal hereditary

properties of labeled graphs with the factorial speed of growth. However, there are

situations where the notion of minimal property is not applicable. A typical example of this type

is given by graphs of large girth. It is known that for each particular value of k, the

graphs of girth at least k are of unbounded tree-width and their speed of growth is

superfactorial, while the limit property of this sequence (i.e., the acyclic graphs) has bounded

tree-width and its speed of growth is factorial. To overcome this difficulty, the notion of

boundary properties of graphs has been recently introduced. In the present talk, we use this

notion in order to identify some classes of graphs which are well-quasi-ordered with

respect to the induced subgraph relation.

Tue, 09 Feb 2010

14:30 - 15:30
L3

Combinatorial theorems in random sets

David Conlon
(Cambridge)
Abstract

The famous theorem of Szemerédi says that for any natural number $k$ and any $a>0$ there exists $n$ such that if $N\ge n$ then any subset $A$ of the set $[N] =\{1, 2,\ldots , N\}$ of size $|A| \ge a N$ contains an arithmetic progression of length $k$. We consider the question of when such a theorem holds in a random set. More precisely, we say that a set $X$ is $(a, k)$-Szemerédi if every subset $Y$ of $X$ that contains at least $a|X|$ elements contains an arithmetic progression of length $k$. Let $[N]_p$ be the random set formed by taking each element of $[N]$ independently with probability $p$. We prove that there is a threshold at about $p = N^{-1/(k-1)}$ where the probability that $[N]_p$ is $(a, k)$-Szemerédi changes from being almost surely 0 to almost surely 1.

There are many other similar problems within combinatorics. For example, Turán’s theorem and Ramsey’s theorem may be relativised, but until now the precise probability thresholds were not known. Our method seems to apply to all such questions, in each case giving the correct threshold. This is joint work with Tim Gowers.

Tue, 09 Mar 2010
12:00
L3

Characterization and Rigidity of the Kerr-Newman Solution

Willie W. Wong
(Cambridge)
Abstract

A celebrated result in mathematical general relativity is the uniqueness of the Kerr(-Newman) black-holes as regular solutions to the stationary and axially-symmetric Einstein(-Maxwell) equations. The axial symmetry can be removed if one invokes Hawking's rigidity theorem. Hawking's theorem requires, however, real analyticity of the solution. A recent program of A. Ionescu and S. Klainerman seeks to remove the analyticity requirement in the vacuum case. They were able to show that any smooth extension of "Kerr data" prescribed on the horizon, satisfying the Einstein vacuum equations, must be Kerr, using a characterization of Kerr metric due to M. Mars. In this talk I will give a characterization for the Kerr-Newman metric, and extend the rigidity result to cover the electrovacuum case.

Subscribe to L3