Anti-Ramsey number of matchings in a hypergraph (Q2231708): Difference between revisions

Given hypergraphs $\mathcal H$ and $\mathcal G$, the anti-Ramsey number $AR(\mathcal H, \mathcal G)$ is the greatest integer $c$ such that no $c$-coloring of the edges of $\mathcal H$ admits a copy of $\mathcal G$ whose edges (using that coloring) are all of distinct colors. This article determines anti-Ramsey numbers for a class of hypergraphs for subhypergraphs with mutually disjoint edges. Let $\mathcal H = \mathcal H(m_1, m_2, m_3)$ be the tripartite hypergraph whose vertices are partitioned $V = V_1 \cup V_2 \cup V_3$, with $|V_i| = m_i$ for each $i \in [3]$, and whose edge set is the set of all $3$-element subsets $e \subseteq V$ such that $|e \cap V_i| = 1$ for each $i \in [3]$. A matching on $\mathcal H$ is a subhypergraph $\mathcal M$ such that no two edges of $\mathcal M$ share a vertex; let $\mathcal M_k$ be the matching consisting of $k$ $3$-vertex edges. Letting $E_{\mathcal H}$ be the set of edges of $\mathcal H$, a $c$-coloring of $\mathcal H$ is a map $\mathcal C : E_{\mathcal H} \to [c]$, and a subgraph $\mathcal G$ of $\mathcal H$ is rainbow (with respect to the coloring $\mathcal C$) if the restriction of $\mathcal C$ to the edges of $\mathcal G$ is one-to-one. For positive integers $m_1$, $m_2$, $m_3$, $k$, let $AR(m_1, m_2, m_3, k) \; {:}{=} \; AR(\mathcal H, \mathcal M_k)$. This paper presents the following results. First, if $2 \leq m_1 \leq m_2 \leq$ $m_3$, then $$ AR(m_1, m_2, m_3, 2) = \left\{ \begin{array}{lr} 1 & \mbox{ if }m_2 \geq 3, \\ 2 & \mbox{ if }m_2 < 3 \leq m_3, \\ 4 & \mbox{ if }m_3 = 2. \end{array} \right. $$ Then using this as the basis for an induction, if $k \geq 3$ and $3k - 2 \leq m_1 \leq m_2 \leq m_3$, then $AR(m_1, m_2, m_3, k) =$ $m_2 m_3 (k - 2) + 1$. The proof is elementary, but longish and intricate.