In this paper, 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 and by Chakrabarti and Khot in this other paper. But I can't figure out the proof of Hajnal's lemma. Hajnal attributes the lemma to Yao and cites this paper. 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.) 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?

  • $\begingroup$ 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. $\endgroup$ – William Hoza Dec 1 '16 at 21:12

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.