Falgas-Ravry–Vaughan conjecture for induced directed stars

Let Sk\vec{S}_k be the directed star on kk vertices, with one center and k1k-1 edges oriented away from it. For an integer k3k\geq 3, let πSk()\pi_{\vec{S}_k}(\emptyset) denote the maximum induced density of Sk\vec{S}_k in a digraph. Define

αk=max0x1kx(1x)k11xk.\alpha_k=\max_{0\leq x\leq 1}\frac{kx(1-x)^{k-1}}{1-x^k}.

Assume the maximum is attained at x=xkx=x_k. Falgas-Ravry–Vaughan's conjecture.

πSk()=αk,\pi_{\vec{S}_k}(\emptyset)=\alpha_k,

and an extremal configuration is obtained by starting with parts A=xkn|A|=x_kn and B=(1xk)n|B|=(1-x_k)n, adding all edges oriented from AA to BB, and iterating this construction inside AA. The cases k=3k=3 and k=4k=4 are known by flag algebras, while the conjecture is open for general kk, with computer-assisted methods becoming difficult as kk grows.

Sources & referencesView supporting material

Primary source

Hao Huang, “On the maximum induced density of directed stars and related problems”, arXiv:1303.3101 (2013).

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.