<p>I sent an email to Péter Hajnal, and he kindly confirmed that the bound in the lemma should be $\Omega(\frac{\Delta_L(G)}{\lceil \delta_L(G) \rceil} n)$.</p>

CC BY-SA 3.0
2016-12-01T18:52:10.320Z
2016-12-01T18:52:10.320Z
William Hoza
<p>In <a href="http://link.springer.com/article/10.1007/BF01206357" rel="noreferrer">this paper</a>, Hajnal states the following lemma:</p>

<blockquote>
  <p>Let $\mathscr{G}_{n, m}$ be the set of all bipartite graphs with $n$ vertices in the left part and $m$ vertices in the right part. Suppose $\mathscr{P} \subseteq \mathscr{G}_{n, m}$ is nontrivial, monotone, and invariant with respect to bipartite graph isomorphisms. Order the set of minimal graphs with property $\mathscr{P}$ lexicographically according to the sorted list of degrees of left vertices, and let $G$ be the first minimal graph with property $\mathscr{P}$ according to this order. Then the zero-error randomized query complexity of $\mathscr{P}$ is $\Omega(\frac{\Delta_L(G)}{\delta_L(G)} n)$, where $\Delta_L(G)$ is the maximum degree of any vertex in the left side of $G$ and $\delta_L(G)$ is the average degree of the vertices in the left side of $G$.</p>
</blockquote>

<p>(In fact, Hajnal actually uses a slight extension of the above lemma.) The same lemma is also used by Gröger in <a href="http://www.inf.u-szeged.hu/actacybernetica/prevvols/10_3/10_3_119_127.pdf" rel="noreferrer">this other paper</a> and by Chakrabarti and Khot in <a href="http://link.springer.com/chapter/10.1007/3-540-48224-5_24" rel="noreferrer">this other paper</a>. But I can't figure out the proof of Hajnal's lemma. Hajnal attributes the lemma to Yao and cites <a href="http://ieeexplore.ieee.org/document/4568293/" rel="noreferrer">this paper</a>. But Yao's paper doesn't actually claim that lemma in that form.</p>

<p>Yao's paper does prove a closely related lemma. (Lemma 5 in Yao's paper, or equivalently Lemma 6 in <a href="http://www.sciencedirect.com/science/article/pii/002200009190003N" rel="noreferrer">this journal version of Yao's paper</a>.) By adapting the proof of the lemma in Yao's paper, I see how to prove Hajnal's lemma <em>under the extra assumption</em> that $\delta_L(G) \geq \Omega(1)$. I'm having trouble with the case that $\delta_L(G)$ is subconstant.</p>

<p>(I'll now assume that the reader is familiar with Yao's proof.) My understanding is that to prove Hajnal's lemma, the idea is to modify Yao's proof by essentially just replacing $\lambda(n)$ with $\delta_L(G)$ and $\mu(n)$ with $\Delta_L(G)$ everywhere. At a high level, with these modifications, Yao's reasoning still makes sense, and shows that to "discover enough missing edges", the query algorithm will need to make at least about $\frac{\Delta_L(G) - 4\delta_L(G)}{\lceil 4 \delta_L(G) \rceil} \cdot \frac{n}{2}$ queries.</p>

<p>The issue is that when $\delta_L(G)$ is subconstant, because of the ceiling operation, that lower bound is only $O(\Delta_L(G) n)$, which is much smaller than the bound $\frac{\Delta_L(G)}{\delta_L(G)} n$ that appears in Hajnal's lemma. (Concretely, the issue is that each set $T_i'$ needs to have an integer number of vertices in it.)</p>

<p>How can the proof be patched?</p>

CC BY-SA 3.0
2016-12-01T21:12:19.223Z
It looks like in all three papers that I mentioned (Hajnal, Gröger, and Chakrabarti-Khot), the authors only actually use the weaker bound $\Omega(\frac{\Delta_L(G)}{\lceil \delta_L(G) \rceil} n)$. There might be other papers that use this lemma, but I don't know of any.
William Hoza
<graph-theory><query-complexity>
What's the proof of this lemma by Hajnal about the randomized query complexity of monotone graph properties?
William Hoza
# What's the proof of this lemma by Hajnal about the randomized query complexity of monotone graph properties?

(Asked by: username_0 on 2016-11-26)

In [this paper](http://link.springer.com/article/10.1007/BF01206357), Hajnal states the following lemma:

> Let $\mathscr{G}\_{n, m}$ be the set of all bipartite graphs with $n$ vertices in the left part and $m$ vertices in the right part. Suppose $\mathscr{P} \subseteq \mathscr{G}\_{n, m}$ is nontrivial, monotone, and invariant with respect to bipartite graph isomorphisms. Order the set of minimal graphs with property $\mathscr{P}$ lexicographically according to the sorted list of degrees of left vertices, and let $G$ be the first minimal graph with property $\mathscr{P}$ according to this order. Then the zero-error randomized query complexity of $\mathscr{P}$ is $\Omega(\frac{\Delta\_L(G)}{\delta\_L(G)} n)$, where $\Delta\_L(G)$ is the maximum degree of any vertex in the left side of $G$ and $\delta\_L(G)$ is the average degree of the vertices in the left side of $G$.

(In fact, Hajnal actually uses a slight extension of the above lemma.) The same lemma is also used by Gröger in [this other paper](http://www.inf.u-szeged.hu/actacybernetica/prevvols/10_3/10_3_119_127.pdf) and by Chakrabarti and Khot in [this other paper](http://link.springer.com/chapter/10.1007/3-540-48224-5_24). But I can't figure out the proof of Hajnal's lemma. Hajnal attributes the lemma to Yao and cites [this paper](http://ieeexplore.ieee.org/document/4568293/). But Yao's paper doesn't actually claim that lemma in that form.

Yao's paper does prove a closely related lemma. (Lemma 5 in Yao's paper, or equivalently Lemma 6 in [this journal version of Yao's paper](http://www.sciencedirect.com/science/article/pii/002200009190003N).) By adapting the proof of the lemma in Yao's paper, I see how to prove Hajnal's lemma *under the extra assumption* that $\delta\_L(G) \geq \Omega(1)$. I'm having trouble with the case that $\delta\_L(G)$ is subconstant.

(I'll now assume that the reader is familiar with Yao's proof.) My understanding is that to prove Hajnal's lemma, the idea is to modify Yao's proof by essentially just replacing $\lambda(n)$ with $\delta\_L(G)$ and $\mu(n)$ with $\Delta\_L(G)$ everywhere. At a high level, with these modifications, Yao's reasoning still makes sense, and shows that to "discover enough missing edges", the query algorithm will need to make at least about $\frac{\Delta\_L(G) - 4\delta\_L(G)}{\lceil 4 \delta\_L(G) \rceil} \cdot \frac{n}{2}$ queries.

The issue is that when $\delta\_L(G)$ is subconstant, because of the ceiling operation, that lower bound is only $O(\Delta\_L(G) n)$, which is much smaller than the bound $\frac{\Delta\_L(G)}{\delta\_L(G)} n$ that appears in Hajnal's lemma. (Concretely, the issue is that each set $T\_i'$ needs to have an integer number of vertices in it.)

How can the proof be patched?

**Tags:** graph-theory, query-complexity

> **Comments:**
> **username_0**: It looks like in all three papers that I mentioned (Hajnal, Gröger, and Chakrabarti-Khot), the authors only actually use the weaker bound $\Omega(\frac{\Delta_L(G)}{\lceil \delta_L(G) \rceil} n)$. There might be other papers that use this lemma, but I don't know of any.  

---

## 1 answers

### Answer by username_0 on 2016-12-01. Score: 5 | Accepted answer

I sent an email to Péter Hajnal, and he kindly confirmed that the bound in the lemma should be $\Omega(\frac{\Delta\_L(G)}{\lceil \delta\_L(G) \rceil} n)$.


---

