L3

Lagrangian submanifolds are an important class of objects in symplectic geometry. They arise in diverse settings: as vanishing cycles in complex algebraic geometry, as invariant sets in integrable systems, as Heegaard tori in Heegaard-Floer theory and of course as "branes" in the A-model of mirror symmetry. We ask the difficult question: when are two Lagrangian submanifolds isotopic? Restricting to the simplest case of Lagrangian spheres in rational surfaces we will give examples where this question has a complete answer. We will also give some very pictorial examples (due to Seidel) illustrating how two Lagrangians can fail to be isotopic.

We shall explain how to give substance to an old dream of Tits, to invent exotic new zeta functions, and discover the skeleton of algebraic varieties (toric manifolds and tropial geometry).

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

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.

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.

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.

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