Mark Budden^a , William Stiles^b

^aDepartment of Mathematics and Computer Science, Western Carolina University, Cullowhee, NC 28723, USA

mrbudden@email.wcu.edu, wsstiles@uncg.edu

The anti-Ramsey number arn(H) of an r-uniform hypergraph is the maximum number of colors that can be used to color the hyperedges of a complete r-uniform hypergraph on n vertices without producing a rainbow copy of H. In this paper, we determine anti-Ramsey numbers for paths of length 2, certain stars and complete hypergraphs, and the complete 3-uniform hypergraph of order 4 with a single hyperedge removed.

Keywords: hyperedge coloring, paths, stars

Mathematics Subject Classification: 05C15, 05C65, 05C55, 05D10

DOI: 10.5614/ejgta.2021.9.2.12

1. Introduction

First defined by Erdos, Simonovits, and S ˝ os [4] in 1973, the anti-Ramsey number of an ´ runiform hypergraph H(r) determines the number of colors needed for the hyperedges of a complete r-uniform hypergraph to guarantee the existence of a rainbow subhypergraph isomorphic to H(r) . While much work has been done on the evaluation of such numbers in the case of graphs (e.g., see [1], [5], [6], and [8]), little work has considered more general uniformities. One exception is the recent work of Ozkahya and Young [7], where anti-Ramsey numbers for hypergraph matchings ¨ were studied. In this article, we determine the anti-Ramsey numbers for r-uniform paths of length

Received: 28 May 2019, Revised: 4 May 2021, Accepted: 10 May 2021.

^bDepartment of Mathematics and Statistics, University of North Carolina at Greensboro 116 Petty Building, PO Box 26170, Greensboro, NC 27402, USA

2, certain stars and complete r-uniform hypergraphs, and the complete 3-uniform hypergraph of order 4 missing a single hyperedge.

We begin with the relevant definitions. Suppose throughout that r ≥ 2. An r-uniform hypergraph H(r) = (V, E) consists of a nonempty set V of vertices and a set E consisting of unordered r-tuples of distinct vertices. Elements of E are called hyperedges. When we wish to specify the underlying hypergraph, we write V (H(r) ) and E(H(r) ) in place of V and E, respectively. We refer to such a hypergraph by just H(r) , including the superscript (r) to emphasize the specific uniformity being considered. If the uniformity is dropped from the notation, it should be assumed that r = 2. The complete r-uniform hypergraph K (r) ⁿ contains n vertices and every r-tuple of distinct vertices forms a hyperedge. If a single hyperedge is removed, we write K (r) ⁿ − e to denote the resulting hypergraph.

The other two types of hypergraph that we will consider fall under the category of trees when r = 2: paths and stars. Let 1 ≤ t < r. The t-tight r-uniform path of length k, denoted P (r) k,t , consists of distinct vertices x1, x2, . . . , xr+(k−1)(r−t) and hyperedges

\[e_i = x_{(r-t)(i-1)+1} x_{(r-t)(i-1)+2} \cdots x_{(r-t)(i-1)+r}, \quad \text{for } 1 \le i \le k.\]

Figure 1 gives some examples of paths with varying parameters. In the special case where t = 1

Figure 1. Examples of paths with various uniformities, lengths, and tightnesses.

and r = 2, we replace Pk,¹ with the usual notation Pk. The t-tight r-uniform star of order p, denoted S (r) p,t , has vertex set V = C ∪ U, where C ∩ U = ∅, |C| = t, and |U| = p − t. The hyperedge set of S (r) p,t consists of all hyperedges that include all vertices in C and some selection of r − t vertices from U. The set C is called the center of the star S (r) p,t . Figure 2 provides some examples of stars with varying parameters. In the special case where t = 1 and r = 2, we replace Sp,¹ with the usual (bipartite) notation K1,p−1.

Figure 2. Examples of stars with various uniformities, orders, and center cardinalities.

For k ≥ 1, a k-coloring of K (r) ⁿ is a map

\[c: E(K_n^{(r)}) \longrightarrow \{1, 2, \dots, k\}.\]

A k-coloring is called exact if it is surjective. Denote the set of all exact k-colorings of K (r) ⁿ by Ck(K (r) ⁿ ). Given an exact k-coloring c of K (r) ⁿ , we say that a subhypergraph H(r) of K (r) ⁿ is rainbow if the restriction of c to H(r) is injective:

\[c|_{H^{(r)}}: E(H^{(r)}) \hookrightarrow \{1, 2, \dots, k\}.\]

If we assume that H(r) is an r-uniform hypergraph of order p that lacks isolated vertices, then for n ≥ p, the anti-Ramsey number arn(H(r) ) is defined to be the maximum k such that some exact k-coloring in Ck(K (r) ⁿ ) lacks a rainbow subhypergraph isomorphic to H(r) . Observe that every n r coloring of K (r) ⁿ results in a rainbow copy of H(r) and |E(H(r) )| colors are required to produce a rainbow H(r) . It follows that

\[|E(H^{(r)})| - 1 \le ar_n(H^{(r)}) \le \binom{n}{r} - 1.\]

The anti-Ramsey number arn(H(r) ) is related to the rainbow number rbn(H(r) ), defined to be the minimum k such that every exact k-coloring of K (r) ⁿ contains a rainbow H(r) (c.f. Section 11.4 of [3]). It follows that

\[rb_n(H^{(r)}) = ar_n(H^{(r)}) + 1,\]

and the reader should be aware that the definition of a rainbow number is sometimes given as the definition of an anti-Ramsey number.

In Section 2, we prove several results for general uniformity. In particular, we show that

\[ar_n(P_{2,t}^{(r)}) = 1\] for all \(n \ge 2r - t\).

We also provide a theorem relating anti-Ramsey numbers for r-uniform complete hypergraphs to anti-Ramsey numbers for certain (n − r)-uniform stars. This result allows us to use some known

results on graphs to obtain anti-Ramsey numbers for certain hypergraphs. The section is concluded with the determination of lower bounds for the anti-Ramsey numbers \(ar_{r+2}(K_{r+1}^{(r)})\).

The anti-Ramsey number for \(K_4^{(3)} - e\) (the complete 3-uniform hypergraph of order 4 with a single hyperedge removed) is the focus of Section 3. We prove a general upper bound and give exact evaluations in the cases n = 5, 6. Section 4 concludes with a few directions for future inquiry.

2. General r-Uniform Results

In this section, we focus on proving a few results that are independent of uniformity. First, we consider the case of paths of length 2.

Theorem 2.1. For all \[n \ge 2r - t\], \(ar_n(P_{2,t}^{(r)}) = 1\).

Proof. Observe that 2 colors are needed to produce a rainbow path of length 2. So, \(ar_n(P_{2,t}^{(r)}) \geq 1\). To prove the other direction, consider an exact 2-coloring of \(K_n^{(r)}\). We claim there exists red and blue hyperedges with non-empty overlap. Otherwise, suppose that \(e_1 \cap e_2 = \emptyset\) with \(e_1\) colored red and \(e_2\) colored blue, where \(e_1, e_2\) are hyperedges in \(K_n^{(r)}\). Any hyperedge that includes vertices from both \(e_1\) and \(e_2\) must be colored red or blue, creating a nontrivial overlap between a red hyperedge and a blue hyperedge. It remains to be shown that for any \(1 \leq t \leq r-2\), there exists a rainbow path \(P_{2,t}^{(r)}\) if and only if there exists a rainbow path \(P_{2,t+1}^{(r)}\).

\((\Longrightarrow)\) Assume there exists a t-tight rainbow path of length 2 with blue hyperedge \(e_1\) and red hyperedge \(e_2\). Without loss of generality, suppose that

\[e_1 = y_1 y_2 \cdots y_{r-t} x_1 x_2 \cdots x_t\] and \(e_2 = x_1 x_2 \cdots x_t z_1 z_2 \cdots z_{r-t}\)

(see the first image in Figure 3). If no (t+1)-tight rainbow path of length 2 exists, then the hyper-

Figure 3. Increasing tightnesses for rainbow paths of length 2.

edge \(e_3 = y_{r-t}x_1x_2\cdots x_tz_1z_2\cdots z_{r-t-1}\) must be blue and the hyperedge \(e_4 = y_2y_3\cdots y_{r-t}x_2x_3\cdots x_tz_1z_{r-t}\) must be red (see the second image in Figure 3). However, \(e_3\) and \(e_4\) now form a (t+1)-tight rainbow path of length 2.

(\(\Leftarrow\)) Assume there exists a (t+1)-tight rainbow path of length 2 with blue hyperedge \(e_1\) and red hyperedge \(e_2\). Without loss of generality, suppose that

\[e_1 = y_1 y_2 \cdots y_{r-t-1} x_1 x_2 \cdots x_{t+1}\] and \(e_2 = x_1 x_2 \cdots x_{t+1} z_1 z_2 \cdots z_{r-t-1}\)

(see the first image in Figure 4). Note that since \(n \geq 2r - t\), there exists some vertex w that is

Figure 4. Decreasing tightnesses for rainbow paths of length 2.

not contained in \(e_1\) or \(e_2\). If no t-tight rainbow path of length 2 exists, then the hyperedge \(e_3 = wx_2x_3\cdots x_{t+1}z_1z_2\cdots z_{r-t-1}\) must be blue and the hyperedge \(e_4 = xy_1y_2\cdots y_{r-t-1}x_1x_2\cdots x_t\) must be red (see the second image in Figure 4). However, \(e_3\) and \(e_4\) now form a t-tight rainbow path of length 2.

Hence, at most 1 color can be used without creating a rainbow path of any given tightness, concluding the proof. \(\Box\)

One particularly useful trick to working with anti-Ramsey numbers of hypergraphs is to construct a natural bijection between exact k-colorings of \(K_n^{(r)}\) and exact k-colorings of \(K_n^{(n-r)}\). Specifically, let

\[c: E(K_n^{(r)}) \longrightarrow \{1, 2, \dots, k\}\]

be an exact k-coloring with \(n-r\geq 2\). Then c induces an exact k-coloring \(\mathcal{I}(c)\) on \(K_n^{(n-r)}\) by taking

\[\mathcal{I}(c)(x_{r+1}x_{r+2}\cdots x_n) := c(x_1x_2\cdots x_r),\]

where the vertex sets of \(K_n^{(r)}\) and \(K_n^{(n-r)}\) are both identified with \(\{x_1, x_2, \dots, x_n\}\). We call \(\mathcal{I}(c)\) the induced coloring of c and observe that

\[\mathcal{I}: \mathcal{C}_k(K_n^{(r)}) \longrightarrow \mathcal{C}_k(K_n^{(n-r)})\]

is a bijection.

Theorem 2.2. For all \[n > m > r \ge 2\], \(ar_n(K_m^{(r)}) = ar_n(S_{n,n-m}^{(n-r)})\).

Proof. Let c : E(K (r) ⁿ ) −→ {1, 2, . . . , k} be an exact k-coloring of K (r) ⁿ and let I(c) be its induced coloring on K (n−r) ⁿ . Equivalently, c is the induced coloring of I(c). We must argue that c contains a rainbow K (r) ^m if and only if I(c) contains a rainbow S (n−r) n,n−m. The hyperedges of a complete runiform hypergraph with vertex set U := {x1, x2, . . . , xm} receive distinct colors under c if and only if the hyperedges containing all of the vertices in V (K (r) ⁿ ) − U, and a subset of m − r of the vertices in U receive distinct colors under I(c). Thus, every exact k-coloring of K (r) ⁿ contains a rainbow K (r) ^m if and only if every exact k-coloring of K (n−r) ⁿ contains a rainbow S (n−r) n,n−^m (for example, see Figure 5).

Figure 5. An exact coloring c of K (4) 7 contains a rainbow K (4) 5 if and only if its induced coloring I(c) of K (3) 7 contains a rainbow S (3) 7,2 .

Applying Theorem 2.2 to known anti-Ramsey numbers on graphs, we can obtain select results on hypergraphs. Erdos, Simonovits, and S ˝ os [4] proved that ´

\[ar_n(K_3) = n - 1\], for all \(n \ge 4\),

from which it follows that

\[ar_n(S_{n,n-3}^{(n-2)}) = n-1, \text{ for all } n \ge 4.\]

Jiang [6] proved that

\[ar_n(K_{1,4}) = n+1\] and \(ar_n(K_4) = \left\lfloor \frac{n^2}{4} \right\rfloor + 1\), for all \(n \ge 5\),

from which Theorem 2.2 implies that

\[ar_5(K_4^{(3)}) = 6\] and \(ar_n(S_{n,n-4}^{(n-2)}) = \left\lfloor \frac{n^2}{4} \right\rfloor + 1\), for all \(n \ge 5\).

The same principal of using induced colorings leads us to the following theorem involving complete hypergraphs.

Theorem 2.3. If r ≥ 2, then

\[ar_{r+2}(K_{r+1}^{(r)}) \ge \frac{(r+2)(r-1)}{2} + \left\lfloor \frac{r+2}{3} \right\rfloor.\]

Proof. Using the concepts introduced in Theorem 2.2, the bijection

\[\mathcal{I}: \mathcal{C}(K_{r+2}^{(r)}) \longrightarrow \mathcal{C}(K_{r+2})\]

sends a rainbow K (r) ^r+1 to a rainbow K1,r+1. One way to maximize the number of colors used in a rainbow K1,r+1-free coloring of Kr+2 is to color edges by maximizing the number of disjoint small cycles, which are each given distinct colors. By the Division Algorithm, there exists unique q, t ∈ Z such that

\[r+2=3q+t\], where \(0 \le t \le 2\).

When t = 0, we can partition the vertices in Kr+2 into q K3-subgraphs, with each K³ receiving its own color. The remaining edges each get their own color, producing a K1,r+1-free coloring of Kr+2 using a total of

\[q + \left(\begin{array}{c} r+2\\2 \end{array}\right) - 3q\]

colors. When t = 1, we partition the vertices into q − 1 K3-subgraphs and a single cycle C⁴ of length four. Giving each cycle and all remaining edges distinct colors gives a total of

\[q + \left(\begin{array}{c} r+2\\2 \end{array}\right) - (3q+1)\]

colors. When t = 2, we partition the vertices into q − 1 K3-subgraphs and a single cycle C⁵ of length five. Following the same color scheme as before, we obtain a total of

\[q + \left(\begin{array}{c} r+2\\2 \end{array}\right) - (3q+2)\]

colors. In all three cases, we have produced a coloring of Kr+2 that lacks a rainbow K1,r+1 using

\[q + \left(\begin{array}{c} r+2\\2 \end{array}\right) - (r+2)\]

colors. Observing that q = b r+2 3 c completes the proof of the theorem.

3. The Anti-Ramsey Number for \(K_4^{(3)}-e\)

Denote by \(K_4^{(3)} - e\) the complete 3-uniform hypergraph of order 4 with a single hyperedge removed. An exact k-coloring of \(K_n^{(3)}\), with \(k \ge 3\) and \(n \ge 4\), contains a rainbow \(K_4^{(3)} - e\) if and only if it contains a \(K_4^{(3)}\) spanned by hyperedges using at least 3 colors. It follows that

\[ar_4(K_4^{(3)} - e) = 2.\]

Beginning with an exact 2-colored \(K_4^{(3)}\) having vertex set \(\{x_1,x_2,x_3,x_4\}\), one can construct an exact k-colored \(K_{k+2}^{(3)}\) that lacks a rainbow \(K_4^{(3)} - e\) by assigning color s (with \(s=3,4,\ldots,k\)) to all hyperedges of the form \(x_ix_jx_{s+2}\) whenever i < s+2 and j < s+2. It follows that

\[ar_n(K_4^{(3)} - e) \ge n - 2.\] (1)

The following theorem proves that this bound is exact when n = 5.

Theorem 3.1. \(ar_5(K_4^{(3)} - e) = 3\).

Proof. It remains to be shown that every exact 4-coloring of \(K_5^{(3)}\) (using say, red, blue, green, and purple) contains a \(K_4^{(3)}\) spanned by hyperedges using at least 3 colors. We will prove this by contradiction. Consider a 4-coloring of \(K_5^{(3)}\) that lacks a \(K_4^{(3)}\) spanned by hyperedgers using at least 3 colors. By Theorem 2.1, there exists a 2-colored \(P_{2,2}^{(3)}\). Without loss of generality, suppose that this path is given by \(x_1x_2x_3x_4\) with \(x_1x_2x_3\) red and \(x_2x_3x_4\) blue. Since no 3-colored \(K_4^{(3)}\)s exist, the subhypergraph induced by \(S:=\{x_1,x_2,x_3,x_4\}\) is a red/blue \(K_4^{(3)}\). Without loss of generality, assume that it has at least as many red hyperedges as it has blue hyperedges. The remaining six hyperedges in the \(K_5^{(3)}\) all contain \(x_5\) and at least one of them is green and another is purple. If any green hyperedge has a vertex from S in common with a purple hyperedge, then a 3colored \(K_4^{(3)}\) is produced. This forces there to only be a single green hyperedge and a single purple hyperedge whose intersection in S is empty. One of these hyperedges must include two vertices from \(\{x_2, x_3, x_4\}\). Suppose it is the green hyperedge, which is given by \(x_2x_3x_5\). Then \(x_1x_4x_5\) is purple and at least one of \(x_1x_2x_4\) and \(x_1x_3x_4\) is red. Suppose the former case. At this point, we have Figure 6. Observe that the subhypergraph induced by \(\{x_1, x_2, x_4, x_5\}\) is red/purple and the subhypergraph induced by \(\{x_2, x_3, x_4, x_5\}\) is blue/green. This gives us a contradiction since no coloring of the hyperedge \(x_2x_4x_5\) satisfies these conditions. It follows that every exact 4-coloring of \(K_5^{(3)}\) contains a \(K_4^{(3)}\) spanned by hyperedges using at least 3 colors.

Theorem 3.2. For all n > 5,

\[ar_n(K_4^{(3)} - e) \le \begin{cases} \frac{1}{4}n(n-2) - 1, & \text{if } n \text{ is even} \\ \frac{1}{4}(n-1)^2 - 1, & \text{if } n \text{ is odd.} \end{cases}\]

Proof. We proceed by weak induction on n, with Theorem 3.1 providing the base case when n=5. Let

\[p = \begin{cases} \frac{1}{4}n(n-2) - 1, & \text{if } n \text{ is even} \\ \frac{1}{4}(n-1)^2 - 1, & \text{if } n \text{ is odd.} \end{cases}\]

Figure 6. A subhypergraph contained in an exact 4-coloring of \(K_5^{(3)}\) that lacks a \(K_4^{(3)}\) spanned by hyperedges using at least 3 colors.

Suppose the theorem is true for n-1 and consider an exact p-coloring of \(K_n^{(r)}\). Label the vertices of this complete hypergraph by \(x_1, x_2, \ldots, x_n\). If no rainbow \(K_4^{(3)} - e\) is contained in this coloring, then by the inductive hypothesis, the subhypergraph induced by \(\{x_1, x_2, \ldots, x_{n-1}\}\) contains hyperedges spanned by at most q colors, where

\[q = \begin{cases} \frac{1}{4}(n-2)^2 - 1, & \text{if } n \text{ is even} \\ \frac{1}{4}(n-1)(n-3) - 1, & \text{if } n \text{ is odd.} \end{cases}\]

The remaining hyperedges are those that contain \(x_n\) and exactly two vertices from \(\{x_1, x_2, \ldots, x_{n-1}\}\). If n is even, then n-1 is odd, and adding in \(\frac{n}{2}\) additional colors forces two such hyperedges to have some vertex in common from \(\{x_1, x_2, \ldots, x_{n-1}\}\). Without loss of generality, suppose that \(x_1x_2x_n\) and \(x_2x_3x_n\) have two of the additional colors. Then the subhypergraph induced by \(\{x_1, x_2, x_3, x_n\}\) contains a rainbow \(K_4^{(3)} - e\), and this resulted from having at least

\[\frac{1}{4}(n-2)^2 - 1 + \frac{n}{2} = \frac{1}{4}n(n-2)\]

colors. Similarly, If n is odd, then n-1 is even, and adding in \(\frac{n+1}{2}\) additional colors forces two such hyperedges to have some vertex in common from \(\{x_1, x_2, \dots, x_{n-1}\}\), forming a rainbow \(K_4^{(3)} - e\).

The subhypergraph induced by \(\{x_1, x_2, x_3, x_n\}\) contains a rainbow \(K_4^{(3)} - e\), and this resulted from having at least

\[\frac{1}{4}(n-1)(n-3) - 1 + \frac{n+1}{2} = \frac{1}{4}(n-1)^2\]

colors. The resulting upper bounds follow for \(ar_n(K_4^{(3)} - e)\).

For \(ar_6(K_4^{(3)}-e)\), we can slightly improve upon the lower bound that is given by (1). Consider the exact 5-coloring of \(K_6^{(3)}\) that is given by the 4 hyperedges shown Figure 7, with all remaining hyperedges colored orange. In this construction, the removal of any two vertices removes 3 colors,

Figure 7. An exact 5-coloring of \(K_6^{(3)}\) (all hyperedges not pictured are assigned the fifth color) that lacks a rainbow \(K_4^{(3)} - e\).

resulting in a 2-colored \(K_4^{(3)}\). Hence,

\[ar_6(K_4^{(3)} - e) \ge 5.\]

Combining this lower bound with Theorem 3.2 results in the following corollary.

Corollary 3.1. \(ar_6(K_4^{(3)} - e) = 5\).

4. Concluding Comments

We conclude by stating a few directions for future inquiry.

• 1. We have not discussed it here, but anti-Ramsey numbers are intrinsically connected with Turan numbers. While little is known about hypergraph Tur ´ an numbers, known results may ´ offer some additional information about their anti-Ramsey counterparts (e.g., see [4] and [7]).
• 2. Using the ideas introduced in the proof of Theorem 2.2, what other hypergraphs are preserved under induced exact colorings? Through examples, we have found that certain cycles correspond with other cycles or matchings under I.
• 3. Finally, what results do induced colorings offer for the determination of traditional Ramsey numbers for hypergraphs (e.g., see [2])? Analogous to Theorem 2.2, a k-coloring c of K (r) ⁿ contains a monochromatic K (r) ^m if and only if the induced coloring I(c) contains a monochromatic S (n−r) n,n−m.

References

• [1] A. Bialostocki, A. Gilboa and Y. Roditty, Anti-Ramsey numbers of small graphs, Ars Combin. 123 (2015), 41–53.
• [2] M. Budden, J. Hiller and A. Rapp, Generalized Ramsey theorems for r-uniform hypergraphs, Australas. J. Combin. 63(1) (2015), 142–152. https://ajc.maths.uq.edu.au/pdf/63/ajc v63 p142.pdf
• [3] G. Chartrand and P. Zhang, Chromatic graph theory, Chapman and Hall, 2008.
• [4] P. Erdos, M. Simonovits and V. S ˝ os, Anti-Ramsey theorems, ´ Colloquia Mathematica Societatis Janos Bolyai 10 (1973), 633–643.
• [5] S. Gilboa, and Y. Roditty, Anti-Ramsey numbers of graphs with small connected components, Graphs Combin. 32 (2016), 649–662.
• [6] T. Jiang, Edge-colorings with no large polychromatic stars, Graphs Combin. 18 (2002), 303– 308.
• [7] L. Ozkahya and M. Young, Anti-Ramsey number of matchings in hypergraphs, ¨ Discrete Math. 313 (2013), 2359–2364.
• [8] I. Schiermeyer, Rainbow numbers for matchings and complete graphs, Discrete Math. 286 (2004), 157–162.