The clique-and-hub conjecture for the hypergraph variational problem

From papers

Let HH be a fixed hypergraph, and let p=p(n)p=p(n) satisfy ncHp1n^{-c_H}\ll p\ll 1. A clique is the collection of all rr-tuples contained in a specified prefix SS of [n][n], while a hub is the collection of all rr-tuples intersecting such a prefix. An edge-weighted rr-graph arises from planting one of these objects when its planted edges have weight 11 and all other edges have weight pp.

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 HH 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

No solutions have been posted yet.