Problems in Graph Theory from Memphis

NEW

Problem: Reconstruct $\Phi_n(G,H)$ as the worst-case least degree-spread forced in a Ramsey copy: for an $n$-vertex graph $F$, let

$$\operatorname{sp}_F(X)=\max_{x\in X}d_F(x)-\min_{x\in X}d_F(x),$$

and let $\Phi_n(G,H)$ be the maximum, over all $n$-vertex graphs $F$, of the minimum $\operatorname{sp}_F(X)$ over vertex sets $X$ spanning a copy of $G$ in $F$ or a copy of $H$ in $\overline F$. The question asks whether

$$\Phi_n(G,H)=r(G,H)-2$$

for all $n\ge r(G,H)$.

Result: The asserted relation is false. Take $G=K_2$, $H=K_4$. Then $r(K_2,K_4)=4$: every graph on $4$ vertices either has an edge or is empty, hence has an independent $4$-set, while the empty graph on $3$ vertices avoids both.

I claim

$$\Phi_5(K_2,K_4)=1.$$

Lower bound: let $F=P_3\cup 2K_1$. Its degrees are $2,1,1,0,0$. Every edge has degree-spread $1$, and the only independent $4$-set consists of the two leaves of $P_3$ and the two isolated vertices, also with spread $1$. Hence $\Phi_5(K_2,K_4)\ge1$.

Upper bound: let $F$ be any graph on $5$ vertices. If some edge joins vertices whose degrees differ by at most $1$, we are done. Otherwise every edge joins degrees differing by at least $2$. Let $\Delta$ be the maximum degree.

If $\Delta=4$, the four nonuniversal vertices all have degrees $1$ or $2$, and no two of them can be adjacent, so they form an independent $4$-set of spread at most $1$.
If $\Delta\le2$, then no degree-$2$ vertex can have a neighbor, contradiction unless the graph is empty; then an independent $4$-set has spread $0$.
If $\Delta=3$, a degree-$3$ vertex has three neighbors, all of degree $1$; the remaining vertex must have degree $0$. Those three degree-$1$ vertices together with the degree-$0$ vertex form an independent $4$-set of spread $1$.

Thus $\Phi_5(K_2,K_4)\le1$, proving equality. Therefore

$$\Phi_5(K_2,K_4)=1<2=r(K_2,K_4)-2,$$

with $5\ge r(K_2,K_4)$. Hence the proposed relation does not hold for all $n\ge r(G,H)$.

Citation: No external citation; the counterexample and proof above are self-contained.