The Solution of Feige’s conjecture by Guruswami, Kothari and Manohar (Re-blogged from “In Theory”)

Luca Trevisan

I’m reblogging here a beautiful post by Luca Trevisan from his blog “In Theory”. The original post appeared a year ago in April 2024. A few weeks after this post was published, Luca sadly passed away at the age of 52.

In this post, Luca masterfully describes the resolution of Feige’s conjecture regarding Moore’s bound for hypergraphs. The conjecture was proved by Guruswami, Kothari and Manohar and the post described a simplified solution by Hsieh, Kothari and Mohanty.

Luca’s blog “In theory” began in March 2006 with a story about  a coyote found in Central Park. Over the years, it featured many excellent mathematical posts, great posts about places— stories from China, Italy, San Francisco, and other places, including a tale with a moral from his 2014 visit to Jerusalem. The blog also touched on food, philosophy, women in science (humorously categorized as “Larry Sammers”), history, politics and more. 

In 2012 Luca solicited essays from gay and lesbian colleagues on the occasion of the Turing centennial, resulting in ten important and moving posts on his blog. For more about Luca Trevisan see here, here and here. One word about the mathematics: the proof of Feige’s conjecture involves Kikuchi graphs, which originated in the work of physicist Ryoichi Kikuchi.  Let be positive integers with . Given a -uniform hypergraph on a vertex set , the Kikuchi graph associated with (and parameter ), is defined as follows: its vertices are -subsets of , and two vertices are adjacent if  their symmetric difference forms a hyperedge of .