We are pleased to announce a half-day meeting with a number of talks
covering several areas in combinatorics. This meeting will take place in
the afternoon of Thursday 30 August 2007, in room A318 of
the London School of Economics. The programme and abstracts of the talks
can be found below.
 |
|
Partitioning Posets |
|
|
Let $P=(X,$<) be a poset. A down-set of $P$ is a subset $A$ of
$X$ such that if $a$ is in $A$ and $b<a$, then $b$ is also in $A$. For
$A$ a down-set of $P$ and $B$ its complement, define
$\displaystyle{\,E(A,B)\;=\;\lbrace\,(a,b)\::\: a\in A,\; b\in B,\; a<b\,\rbrace.}$
This defines an analogue of graph cuts for posets. In this talk we
address the following natural questions: how large can $|E(A,B)|$ be in
general and how difficult is it to maximise $|E(A,B)|$ computationally,
for a given poset? We also consider natural extensions of these questions
for order respecting partitions into more than two parts. |
|
|
|
| |
|
Improper colouring of weighted grid and hexagonal
graphs |
|
|
Motivated by a frequence allocation problem, we study the improper
coloration of weighted graphs and more precisely of weighted subgraph of
the triangular grid. We give approximation algorithms to find such
colorations. |
|
|
|
| |
|
Pseudorandomness and small subgraphs |
|
|
For a fixed $0<p<1$ we say that a sequence
$(G_n)_{n=1}^\infty$ of graphs is $p$-pseudorandom if (i) the
number of edges $e(G_n)=(1+o(1))\,p\,{n\choose 2}$, and (ii) the number
of not necessarily induced labelled copies of $C_4$ in $G_n$ is
$(1+o(1))\,p^4\,n^4$, where $o(1)\to 0$ as $n\to\infty$.
Thomason and Chung and Graham observed that the properties above are
equivalent to a number of other graph properties that are typically
satisfied by random graphs (hence the name "pseudorandom").
One interesting question is whether $C_4$ above can be replaced by any
fixed graph $H$. In other words, is it true that if $H$ is fixed and a
sequence of $(G_n)_{n=1}^\infty$ of graphs satisfies
(i) the number of edges $e(G_n)=(1+o(1))\,p\,{n\choose 2}$,
and
(ii) the number of not necessarily induced labelled copies of $H$
in $G_n$ is $(1+o(1))\,p^{e(H)}\,n^{v(H)}$, where $o(1)\to 0$ as
$n\to\infty$,
then $(G_n)_{n=1}^\infty$ is $p$-pseudorandom?
In my talk I will discuss known and related results and open questions. |
|
|
|
| |
|
List colouring constants of triangle-free graphs |
|
|
Let $G=(V,E)$ be a graph. A list assignment to vertices of
$G$ associates a list $L(v)$ of available colours to each vertex
$v\in V$. A proper $L$-colouring of $G$ is a proper colouring,
i.e., a colouring in which neighbours have different colours, such that
the colour of each vertex $v$ belongs to $L(v)$.
Given a colour $c$ in $L=\bigcup_{v\in V}L(v)$, we denote
by $G_c$ the graph induced on all vertices $v$ with $c\in L(v)$, i.e.,
$\displaystyle{G_c\:=\:G[\{v\in V\:|\:c\in L(v)\}]}$.
By $\Delta$ we denote the integer number $\max_{c\in L}\Delta(G_c)$. Let
$\ell=\min_v|L(v)|$. It was conjectured by Reed that if
$\ell\geq\Delta+1$ then $G$ admits a proper $L$-colouring. Bohman and
Holzman provided a counter-example to this conjecture. Reed and Haxell
proved a sufficient linear bound of type, respectively,
$\ell\geq2\:e\:\Delta$ and $\ell\geq2\:\Delta$ for the existence of a
proper $L$-colouring. Furthermore Sudakov and Reed proved that the
conjecture is asymptotically true. An intriguing open question is then
Is there any constant $C$ such that for every $G$ and $L$ as
above with $\ell\geq \Delta+C$, $G$ admits a proper
$L$-colouring?
We prove the following theorem which in particular provides an answer to
the above question for triangle free graphs:
Theorem
There exists an absolute constant $K$ such that if each subgraph $G_c$
is triangle free and $\ell\geq\frac{K\:\Delta}{\log\Delta}$, then $G$
admits a proper $L$-colouring.
Joint work with Bruce Reed. |
|
|
|
| |
|
Partitioning two-coloured complete graphs into monochromatic
cycles |
|
|
A conjecture due to Lehel states that for any two-edge-coloured
complete graph on $n$ vertices there exist two vertex-disjoint cycles of
opposite colours which cover all the vertices of the graph. We show that
the conjecture holds when $n$ is sufficiently large. |
