4
$\begingroup$

Definition. $h(n_1,n_2)$ is the least number $m$ such that, if the edges of $K_m$ are colored with two colors, $1$ and $2,$ then for some color $i\in\{1,2\}$ there is a set $W\subseteq V(K_m)$ such that $|W|=n_i$ and every triangle in $W$ has an odd number of edges of color $i;$ in other words, for some $i\in\{1,2\},$ the graph consisting of the edges of color $i$ has an induced subgraph $H$ of order $n_i$ such that $H$ has at most two components, and each component of $H$ is a clique.

Question 1. Is there any literature on $h(n_1,n_2)$ ?

Question 2. Is $h(4,5)=8$ ?

Here are some easy bounds for $h(n_1,n_2)$ in terms of ordinary Ramsey numbers.

Definition. The Ramsey number $R(n_1,n_2;d)$ is the least number $m$ such that, given an $m$-element set $V$ and any set $S\subseteq\binom Vd,$ we can find a set $W\subseteq V$ such that either $|W|=n_1$ and $\binom Wd\cap S=\emptyset,$ or else $|W|=n_2$ and $\binom Wd\subseteq S.$

Definition. As in my previous question A funny kind of Ramsey number, $f(n)$ is the least number $m$ such that, given an $m$-element set $V$ and any set $S\subseteq\binom V3,$ we can find an $n$-element set $X\subseteq V$ such that, for each $4$-element set $Y\subseteq X,$ we have $|\binom Y3\cap S|\equiv0\pmod2.$

Upper bound: $h(m+1,n+1)\le R(m,n;2)+1.$

Lower bound: $f(h(m,n))\ge R(m,n;3).$

Regarding $h(4,5),$ I know that $$8\le h(4,5)\le10.$$ On the one hand, $h(4,5)\le R(3,4;2)+1=10.$ On the other hand, to see that $h(4,5)\gt7,$ take a Hamiltonian cycle $C$ in $K_7$ and color the edges of $C$ with color $2$ and the rest with color $1.$ (This is the simplest of a whole bunch of $7$-point counterexamples.) I have not found a counterexample to the conjecture that $h(4,5)=8.$

$\endgroup$
4
$\begingroup$

The statement $h(4,5)=8$ is true. It can be checked by enumerating all 8-vertex graphs (a total of 12346) and check them one by one.

For those who want to double-check, there are 48 graphs in which there is exactly one instance of $W$, and 43 in which there are two.

$\endgroup$
  • $\begingroup$ Could you provide some details on how to (efficiently) carry out a computation such as this? This is probably standard, so if instead there is a reference you'd recommend, I would be grateful. $\endgroup$ – Andrés E. Caicedo Jul 3 '18 at 17:06
  • 2
    $\begingroup$ The graphs are generated by B.D.Mckay's program geng, and the computation on a individual graph is brute-force: simply enumerate all the size-4 and size-5 sets of the graph, and test whether there is a clique or a union of two cliques. $\endgroup$ – LeechLattice Jul 3 '18 at 17:11
  • $\begingroup$ Thank you for your answer! In my (tedious and error-prone) pen-and-paper work, I seemed to find 19 7-vertex graphs with no instance of W. How close is that to the correct number? $\endgroup$ – bof Jul 4 '18 at 0:36
  • 1
    $\begingroup$ My answer is 21. The graphs are shown in here. $\endgroup$ – LeechLattice Jul 4 '18 at 1:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.