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

About 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

Primary source

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.