The clique-and-hub conjecture for the hypergraph variational problem
The clique-and-hub conjecture for the hypergraph variational problem
Let be a fixed hypergraph, and let satisfy . A clique is the collection of all -tuples contained in a specified prefix of , while a hub is the collection of all -tuples intersecting such a prefix. An edge-weighted -graph arises from planting one of these objects when its planted edges have weight and all other edges have weight .
Clique-and-hub conjecture. The variational problem is asymptotically optimized by planting a clique and a hub.
The conjecture extends the graph case, where cliques and hubs describe the asymptotically optimal constructions. It is true for graphs and, as stated in the source, also when is a clique, but it fails in general for hypergraphs.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Yang P. Liu and Yufei Zhao, “On the upper tail problem for random hypergraphs”, arXiv:1910.02916 (2020).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.