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.
References
Primary source
Yang P. Liu and Yufei Zhao, “On the upper tail problem for random hypergraphs”, arXiv:1910.02916 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.