Pith. sign in

REVIEW 1 cited by

Edge-coloring a graph $G$ so that every copy of a graph $H$ has an odd color class

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2307.01314 v3 pith:2XRCUZV5 submitted 2023-07-03 math.CO

classification math.CO
keywords graphclasscodecolorcopyeveryalonbound
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Odd Ramsey numbers of multipartite graphs and hypergraphs

    math.CO 2025-07 conditional novelty 6.0 of 10

    For every fixed t and k, r_odd(K_{n,n}, K_{2,t}) = n/t + o(n) and r_odd(K^{(k)}_{n,...,n}, K_{1,...,1,2,2}) = n/2 + o(n).

Pith tools