Skip to main content
Theoretical Computer Science

Return to Answer

added 169 characters in body
Source Link
Student
Student
  • 654
  • 3
  • 11

Two things come to mind when I hear "bipartite expanders"

  • The only proof we have about existence of Ramanujan expanders at every size is through bipartite expanders. The "Interlacing families" construction of Marcus-Spielman-Srivastava effectively settles for the case of bipartite graphs what has been conjectured by Bilu and Linial to be true for all graphs - that every graph has a Ramanujan $\mathbb{Z}_2$ signing. [http://arxiv.org/abs/1304.4132]

  • The work by Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson about how entropy can help understand the construction of optimal lossless expanders and zig-zag product seems to be essentially focussed on bipartite expanders. [ http://dash.harvard.edu/bitstream/handle/1/3330492/Vadhan_CondLosslessExpanders.pdf?sequence=2 ][ http://arxiv.org/abs/math/0406038 ]

Seems all optimality results about expanders are about when they are bipartite? May be this is because somehow our technologies are more tuned to control the upper edge of graph spectrum and only with bipartiteness does it imply something for the whole. (MSS result can in principle be generalized for a larger class of expanders but this larger class is not as conveniently describable)

Two things come to mind when I hear "bipartite expanders"

  • The only proof we have about existence of Ramanujan expanders at every size is through bipartite expanders. The "Interlacing families" construction of Marcus-Spielman-Srivastava effectively settles for the case of bipartite graphs what has been conjectured by Bilu and Linial to be true for all graphs - that every graph has a Ramanujan $\mathbb{Z}_2$ signing.

  • The work by Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson about how entropy can help understand the construction of optimal lossless expanders and zig-zag product seems to be essentially focussed on bipartite expanders.

Seems all optimality results about expanders are about when they are bipartite? May be this is because somehow our technologies are more tuned to control the upper edge of graph spectrum and only with bipartiteness does it imply something for the whole. (MSS result can in principle be generalized for a larger class of expanders but this larger class is not as conveniently describable)

Two things come to mind when I hear "bipartite expanders"

  • The only proof we have about existence of Ramanujan expanders at every size is through bipartite expanders. The "Interlacing families" construction of Marcus-Spielman-Srivastava effectively settles for the case of bipartite graphs what has been conjectured by Bilu and Linial to be true for all graphs - that every graph has a Ramanujan $\mathbb{Z}_2$ signing. [http://arxiv.org/abs/1304.4132]

  • The work by Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson about how entropy can help understand the construction of optimal lossless expanders and zig-zag product seems to be essentially focussed on bipartite expanders. [ http://dash.harvard.edu/bitstream/handle/1/3330492/Vadhan_CondLosslessExpanders.pdf?sequence=2 ][ http://arxiv.org/abs/math/0406038 ]

Seems all optimality results about expanders are about when they are bipartite? May be this is because somehow our technologies are more tuned to control the upper edge of graph spectrum and only with bipartiteness does it imply something for the whole. (MSS result can in principle be generalized for a larger class of expanders but this larger class is not as conveniently describable)

Source Link
Student
Student
  • 654
  • 3
  • 11

Two things come to mind when I hear "bipartite expanders"

  • The only proof we have about existence of Ramanujan expanders at every size is through bipartite expanders. The "Interlacing families" construction of Marcus-Spielman-Srivastava effectively settles for the case of bipartite graphs what has been conjectured by Bilu and Linial to be true for all graphs - that every graph has a Ramanujan $\mathbb{Z}_2$ signing.

  • The work by Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson about how entropy can help understand the construction of optimal lossless expanders and zig-zag product seems to be essentially focussed on bipartite expanders.

Seems all optimality results about expanders are about when they are bipartite? May be this is because somehow our technologies are more tuned to control the upper edge of graph spectrum and only with bipartiteness does it imply something for the whole. (MSS result can in principle be generalized for a larger class of expanders but this larger class is not as conveniently describable)