Recently, Alon introduced the notion of an $H$-code for a graph $H$: a collection of graphs on vertex set $[n]$ is an $H$-code if it contains no two members whose symmetric difference is isomorphic to $H$. Let $D_{ H}(n)$ denote the maximum possible cardinality of an $H$-code, and let $d_{ H}(n)=D_{ H}(n)/2^{ n \choose 2}$. Alon observed that a lower bound on $d_{ H}(n)$ can be obtained by attaining an upper bound on the number of colors needed to edge-color $K_n$ so that every copy of $H$ has an odd color class. Motivated by this observation, we define $g(G,H)$ to be the minimum number of colors needed to edge-color a graph $G$ so that every copy of $H$ has an odd color class. We prove $g(K_n,K_5) \le n^{ o(1)}$ and $g(K_{ n,n}, C_4)= n/2+o(n)$. The first result shows $d_{ K_5}(n) \ge \frac{ 1}{ n^{ o(1)}}$ and was obtained independently in arXiv:2306.14682.
Categories: math.CO