All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD3-S1-T1.2
Paper Title Type Graphs and Small-Set Expansion
Authors Lei Yu, Nankai University, China; Venkat Anantharam, University of California, United States; Jun Chen, McMaster University, Canada
Session D3-S1-T1: Combinatorics & Information Theory
Chaired Session: Wednesday, 14 July, 22:00 - 22:20
Engagement Session: Wednesday, 14 July, 22:20 - 22:40
Abstract In this paper, we study the \emph{type graph}, namely a bipartite graph induced by a joint type. We study the maximum edge density of induced bipartite subgraphs of this graph having a number of vertices on each side on an exponential scale. This can be seen as an isoperimetric problem. We provide asymptotically sharp bounds for the exponent of the maximum edge density as the blocklength goes to infinity. We also study the biclique rate region of the type graph, which is defined as the set of $\left(R_{1},R_{2}\right)$ such that there exists a biclique of the type graph which has respectively $e^{nR_{1}}$ and $e^{nR_{2}}$ vertices on the two sides. We provide asymptotically sharp bounds for the biclique rate region as well. We also apply similar techniques to strengthen small-set expansion theorems.