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

About 7 years old · traced to

Let HH be a fixed hypergraph, and let p=p(n)p=p(n) satisfy n−cH≪p≪1n^{-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.

References

Primary source

Yang P. Liu and Yufei Zhao, “On the upper tail problem for random hypergraphs”, arXiv:1910.02916 (2020).

Progress summary

Never refreshed

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.