## Archive for November, 2015

### Entropy and Sidorenko’s conjecture — after Szegedy

November 18, 2015

Here is a simple but important fact about bipartite graphs. Let $G$ be a bipartite graph with (finite) vertex sets $X$ and $Y$ and edge density $\alpha$ (meaning that the number of edges is $\alpha |X||Y|$). Now choose $(x_1,x_2)$ uniformly at random from $X^2$ and $(y_1,y_2)$ uniformly at random from $Y^2$. Then the probability that all of $x_1y_1, x_1y_2, x_2y_1$ and $x_2y_2$ are edges is at least $\alpha^4$.

The proof is very simple. For each $x$, let $f_x:Y\to\{0,1\}$ be the characteristic function of the neighbourhood of $x$. That is, $f_x(y)=1$ if $xy$ is an edge and $0$ otherwise. Then $\sum_{x,y}f_x(y)$ is the sum of the degrees of the $x\in X$, which is the number of edges of $G$, which is $\alpha |X||Y|$. If we set $f=\sum_{x\in X}f_x$, then this tells us that $\sum_{y\in Y}f(y)=\alpha|X||Y|$. By the Cauchy-Schwarz inequality, it follows that $\sum_{y\in Y}f(y)^2\geq\alpha^2|X|^2|Y|$.

But by the Cauchy-Schwarz inequality again,
$(\sum_{y\in Y}f(y)^2)^2=(\sum_{y\in Y}\sum_{x_1,x_2\in X}f_{x_1}(y)f_{x_2}(y))^2$
$= (\sum_{x_1,x_2\in X}\sum_{y\in Y}f_{x_1}(y)f_{x_2}(y))^2$
$\leq |X|^2\sum_{x_1,x_2\in X}(\sum_{y\in Y}f_{x_1}(y)f_{x_2}(y))^2$
$=|X|^2\sum_{x_1,x_2\in X}\sum_{y_1,y_2\in Y}f_{x_1}(y_1)f_{x_2}(y_1)f_{x_1}(y_2)f_{x_2}(y_2).$
That last expression is $|X|^2$ times the number of quadruples $x_1,x_2,y_1,y_2$ such that all of $x_1y_1, x_1y_2, x_2y_1$ and $x_2y_2$ are edges, and our previous estimate shows that it is at least $\alpha^4|X|^4|Y|^2$. Therefore, the probability that a random such quadruple consists entirely of edges is at least $\alpha^4$, as claimed (since there are $|X|^2|Y|^2$ possible quadruples to choose from). (more…)

### Interesting times in academic publishing

November 10, 2015

In this post I want briefly to mention four current goings on in the world of academic publishing.

First, I’ll just briefly say that things are going well with the new journal Discrete Analysis, and I think we’re on course to launch, as planned, early next year with a few very good accepted papers — we certainly have a number of papers in the pipeline that look promising to me. Of course, we’d love to have more.

Secondly, a very interesting initiative has recently been started by Martin Eve, called the Open Library of Humanities. The rough idea is that they provide a platform for humanities journals that are free to read online and free for authors (or, as some people like to say, are Diamond OA journals). Perhaps the most interesting aspect of this initiative is that it is funded by a consortium of libraries. Librarians are the people who feel the pain of ridiculous subscription prices, so they have great goodwill towards people who are trying to build new and cheaper publication models. I think there is no reason that the sciences couldn’t do something similar — in fact, it should be even easier to find money.
(more…)

### Gil Kalai starts Polymath10

November 5, 2015

I’ve already mentioned this on Google Plus, but my readership there is different from my readership here, so it seems a good idea to write a similar post here, to give what publicity I can to the fact that Gil Kalai has started a new Polymath project. The problem he would like solved (and I would very much like to see it solved too) is the famous delta-systems or sunflower conjecture of Erdős and Rado.

The problem, as with many problems in combinatorics, is easy to state, but fascinatingly hard to solve. It is a classic extremal problem, in that it asks how big some combinatorial object needs to be before it is guaranteed to contain a subobject of some particular kind. In this case, the object is a $k$uniform hypergraph, which just means a collection of sets of size $k$. The subobject one would like to find is a sunflower of size $r$, which means a collection of sets $A_1,\dots,A_r$ such that we can find disjoint sets $H, P_1,\dots,P_r$ with the $P_i$ disjoint and with $A_i=H\cup P_i$ for each $i$. I have used the letters $H$ and $P$ to stand for “head” and “petal” — $H$ is the head of the sunflower and $P_1,\dots,P_r$ are the petals. (more…)