← All problems

The conjecture that an off-diagonal common pair has a common component

3 years old · traced to

Let H1H_1 and H2H_2 be graphs, and let p∈(0,1)p\in(0,1). A pair (H1,H2)(H_1,H_2) is (p,1−p)(p,1-p)-common when it satisfies the off-diagonal common-pair inequality for every complementary pair of graphons. Common-component conjecture. If there exists p∈(0,1)p\in(0,1) such that (H1,H2)(H_1,H_2) is (p,1−p)(p,1-p)-common, then at least one of H1H_1 or H2H_2 is common. The theorem exhibiting a pair with an uncommon component shows that both components need not be common, while this weaker assertion remains open.

References
  1. Natalie Behague, Natasha Morrison and Jonathan A. Noel, “Off-Diagonal Commonality of Graphs via Entropy”, arXiv:2307.03788 (2023).

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.