← All problems

Minimum semidefinite rank conjecture for graphs of large girth

10 years old · traced to

Let GG be a connected graph on n≥2n\geq 2 vertices, and let k≥4k\geq 4 be an integer. The minimum semidefinite rank msr(G){\rm msr}(G) is the smallest rank among all positive semidefinite Hermitian matrices with graph GG. The girth of GG is the length of its shortest cycle.

Large-girth minimum semidefinite rank conjecture. If GG has girth at least kk, then

msr(G)≥(k−2k)n.{\rm msr}(G)\geq \left(\frac{k-2}{k}\right)n.

This conjecture seeks to generalize the known lower bound msr(G)≥n/2{\rm msr}(G)\geq n/2 for connected triangle-free graphs, viewing triangle-freeness as a girth lower bound. Its status is not determined by the supplied source information.

References

2 papers in this index state this conjecture (2016–2017). The statement above is taken from the most recent of them; the others are arXiv:1606.00697.

Source: Louis Deaett and H. Tracy Hall, “Orthogonal representations of Steiner triple system incidence graphs”, arXiv:1708.07741 (2017).

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.