Chennai Mathematical Institute


3.30-4.30 pm, Seminar Hall
R.K. Rubugunday Distinguished Lecture
The girth of graphs and the limits of two bit probes

Jaikumar Radhakrishnan
TIFR, Mumbai.


The Moore bound relates the minimum degree of a graph, its girth and its number of vertices. Alon, Hoory and Linial showed that the same bound holds with the minimum degree replaced by the average degree. We will derive the result of Alon, Hoory and Linial by considering random walks on graphs and entropy.

We will consider the bit-probe complexity of the set membership, where a set S of size n from a universe of size m is to be represented as a bit vector in order to answer membership queries of the form "Is x in S?" by probing the bit vector at t places. Alon and Feige showed that a two-probe data structures for this problem can be based on graphs with large girth. In particular, they showed that for n < log m, one can obtain a data structure that uses O( m n log ((log m) / n) / log m) bits. We improve their construction and also show a related lower bound: O(m^{1- 1/cn}) bits suffice and Omega(m^{1-1/dn}) bits are necessary (for some constants c > d). Both our bounds involve considerations of degree and girth.

(These results were obtained jointly with S Ajesh Babu and Mohit Garg.)