coloringgraph theory
I am reading about Lovász Lemma (in these notes). In the Remark below Theorem 4.3 the it is claimed that we can extend the allowed number to $\frac{l}{2e}$ by using the more general version of the LLL (wikipedia calls it the asymmetric one). Could you please tell me how to prove this?
Remark: Here $e$ denotes Euler's number.
Good so far. If $G$ has $e$ edges, then $\overline{G}$ has $\binom{v}{2}-e$ edges. And since $G$ and $\overline{G}$ are both planar $e \leq 3v-6$ and $\binom{v}{2}-e \leq 3v-6$ which combine to imply $v \leq 10$. This leaves $v \in \{0,1,\ldots,10\}$.
Since $G$ is self-complementary, it has the same number of edges as $\overline{G}$. Hence $e=\binom{v}{2}-e$, and $\binom{v}{2}$ must be even. This leaves $\{0,1,4,5,8,9\}$.
Easy examples exist for $v \in \{0,1,4,5\}$ (a $4$-vertex path and a $5$-cycle in the non-trivial cases). The following is a self-complementary $8$-vertex planar graph:
The graph is drawn along with its complement, and an isomorphism between the two is indicated by the colours. (Source: University of California, Santa Cruz notes: pdf.)
There are $36$ non-isomorphic $9$-vertex self-complementary graphs (according to http://oeis.org/A000171). They are included in McKay's data: http://cs.anu.edu.au/~bdm/data/graphs.html One could exclude the possibility of a $9$-vertex self-complementary graph by finding a $K_{3,3}$ or $K_5$ subdivison (or $K_{3,3}$ or $K_5$ minor) in each of these graphs $36$ graphs.
This is too much legwork for me, so I'll instead refer to this paper:
J. Battle, F. Harary and Y. Kodama, Every planar graph with nine points has a nonplanar complement, Bull. Amer. Math. Soc. 68 (1962), 569-571.
A direct corollary is that there are no $9$-vertex self-complementary planar graphs. We conclude that the maximum number of vertices in a self-complementary planar graph is $8$.
We also find that there are no disconnected self-complementary planar graphs. We can prove this by inspection of McKay's data. The self-complementary (planar) graphs on $4$ or $5$ vertices are drawn below:
And all $8$-vertex self-complementary graphs are connected (whether or not they are planar).
For $a, b\in V(K_n)$, we will say that $a\sim b$ if $ab$ is coloured. Of course $\sim$ is a symmetrical relation.
Then, given $u, v, w\in V(K_n)$ such that $u\sim v$ and $v\sim w$, we must have $u\sim w$ (otherwise the triangle $\triangle uvw$ would have an even number of edges coloured), therefore $\sim$ is a transitive relation, so the graph
$$G = (V(K_n), \{e\in E(K_n) : e\text{ is coloured}\})$$
must consist of several complete connected components. If there are $3$ components, however, we can choose a vertex of each and they will form a triangle with no coloured edges, so the number of components must be at most $2$.
With $2$ connected components, one must have $k$ and the other $n-k$ vertices, totalizing $\begin{aligned}\binom{k}{2} + \binom{n-k}{2} = \frac{n^2-n}{2}+k(n-k)\end{aligned}$ coloured edges, which is minimum when $\begin{aligned}k = \left\lfloor \frac{n}{2} \right\rfloor\end{aligned}$.
Here is an example for $n = 7$:
Best Answer
The "more precise version of the Local Lemma" does not refer to the asymmetric version; rather, it refers to the version which checks the inequality $ep(d+1)\le 1$ rather than the inequality $4pd \le 1$. (In Molloy and Reed, this is Remark 4.1.)
The proof using this version is almost identical. With the condition that each color is acceptable for $\frac{\ell}{2e}$ neighbors of any one vertex, we argue that $|E_x| \le \frac{\ell^2}{2e}$ and $|E_y| \le \frac{\ell^2}{2e}$.
The one extra detail that needs to be supplied is that $E_x$ and $E_y$ both contain the event $A_{i,e}$ that we're looking at - which we don't need to count in $d$. Therefore $A_{i,e}$ is mutually independent of all but at most $\frac{\ell^2}{e}$ events counting itself. This means we are allowed to set $d = \frac{\ell^2}{e}-1$, and satisfy the inequality $ep(d+1) \le 1$ needed to apply the Local Lemma.