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.$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Jul 3, 2018 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
    Commented Jul 3, 2018 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
    Commented Jul 4, 2018 at 0:36
  • 1
    $\begingroup$ My answer is 21. The graphs are shown in here. $\endgroup$
    – LeechLattice
    Commented Jul 4, 2018 at 1:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .