Rigidity of direction-length frameworks
Abstract
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.
Shadows and intersections: stability and new proofs
Abstract
Hamilton cycles in random geometric graphs
Abstract
The Gilbert model of a random geometric graph is the following: place points at random in a (two-dimensional) square box and join two if they are within distance $r$ of each other. For any standard graph property (e.g. connectedness) we can ask whether the graph is likely to have this property. If the property is monotone we can view the model as a process where we place our points and then increase $r$ until the property appears. In this talk we consider the property that the graph has a Hamilton cycle. It is obvious that a necessary condition for the existence of a Hamilton cycle is that the graph be 2-connected. We prove that, for asymptotically almost all collections of points, this is a sufficient condition: that is, the smallest $r$ for which the graph has a Hamilton cycle is exactly the smallest $r$ for which the graph is 2-connected. This work is joint work with Jozsef Balogh and B\'ela Bollob\'as
The edge correlation of random forests
Abstract
The conjecture was made by Pemantle that a forest chosen uniformly at random from all forests in any finite graph G has the edge-negative association property. We use enumerative methods to show that this conjecture is true for n large enough when G is a complete graph on n vertices and derive related results for random trees.
Cycles in directed graphs
Abstract
There are many theorems concerning cycles in graphs for which it is natural to seek analogous results for directed graphs. I will survey
recent progress on certain questions of this type. New results include
(i) a solution to a question of Thomassen on an analogue of Dirac’s theorem
for oriented graphs,
(ii) a theorem on packing cyclic triangles in tournaments that “almost” answers a question of Cuckler and Yuster, and
(iii) a bound for the smallest feedback arc set in a digraph with no short directed cycles, which is optimal up to a constant factor and extends a result of Chudnovsky, Seymour and Sullivan.
These are joint work respectively with (i) Kuhn and Osthus, (ii) Sudakov, and (iii) Fox and Sudakov.
Synchronization and homomorphisms
Abstract
A graph homomorphism is a mapping of vertices which takes edges to edges. The endomorphisms of a graph (homomorphisms to itself) form a submonoid of he full transformation monoid on the vertex set. In the other direction, there is a construction of a graph from a transformation monoid, which will be described in the talk. Composing these maps gives closure operators on graphs and on monoids which have some interesting properties. There are also connections with finite automata and permutation groups.