A note on Ramsey numbers for Berge-G hyper graphs
Maria Axenovich Andras Gyarfas






A note on Ramsey numbers for Berge-G hypergraphs
    Maria AxenovichKarlsruhe Institute of Technology, Karlsruhe, GermanyAndrás GyárfásRenyi  Institute of Mathematics, Budapest, HungaryResearch supported in part by
NKFIH Grant No. K116769.
    
==============================================================================================================================================================================================




For a graph G=(V,E),  a hypergraph H is called Berge-G if there is a bijection ϕ: E(G) → E(H) such that for each e∈ E(G), e ⊆ϕ(e).  The set of all Berge-G hypergraphs is denoted (G).

For integers k≥ 2, r≥ 2, and a graph G, let the Ramsey number R_r((G), k) be the smallest integer n such that no matter how the edges of a complete r-uniform n-vertex hypergraph are colored with k colors, there is a copy of a monochromatic Berge-G subhypergraph. Furthermore, let R((G),k) be the smallest integer n such that no matter how all subsets an n-element set are colored with k colors, there is a monochromatic copy of a Berge-G hypergraph.

We give an upper bound for R_r((G),k) in terms of graph Ramsey numbers. In particular, we prove that when G becomes acyclic after removing some vertex, R_r((G),k)≤ 4k|V(G)|+r-2, in contrast with classical multicolor Ramsey numbers.

When G is a triangle (or a K_4), we find sharper bounds and some exact results and  determine some “small” Ramsey numbers:




  * k/2 - o(k)  ≤ R_3((K_3)), k) ≤  3k/4+ o(k),



  * For any odd integer t 3,  R((K_3),2^t-1)=t+2,


  * 2^ck≤ R_3((K_4),k)≤ e(1+o(1))(k-1)k!,


  * R_3((K_3),2)=R_3((K_3),3)=5,  R_3((K_3),4)=6,  R_3((K_3),5)=7, R_3((K_3),6)=8,  R_3((K_3,8)=9,  R_3((K_4),2)=6.











§ INTRODUCTION


For a graph G, a family  (G)  consists of hypergraphs  H each with |E(G)| distinct hyperedges so that
for each xy∈ E(G),  there is a hyperedge e_xy of H such that
 ϕ(x),ϕ(y) ∈  e_xy and e_xy≠ e_x'y' if xy≠ x'y', for an injective map ϕ: V(G)→ V(H).
 Here, we shall always denote the vertex set of F as V(F) and the edge set of F as E(F), for a graph or a hypergraph F. A copy of a graph F in a graph G is a subgraph of G isomorphic to F. When clear from context, we shall drop the word “copy" and just say that there is F in G.

The members of (G) are called Berge-G hypergraphs.
We call  a copy G' of G, where G'= (ϕ(V(G)), {ϕ(x)ϕ(y):  xy∈ E(G)}),  the underlying  graph of the Berge-G hypergraph.



The Ramsey number R_r(, k) is the smallest integer n such that no matter how the edges of a complete r-uniform n-vertex hypergraph, that we denote K^r_n,  are colored with k colors, there is a monochromatic  subhypergraph from . We always assume that k≥ 2, r≥ 2, and simply write K_n for K^2_n. The classical k-color Ramsey number for a graph G (uniformity 2) is denoted R(G, k), i.e., R(G, k) = R_2({G}, k).  When we do not restrict our attention to uniform hypergraphs, we define the Ramsey number R((G), k) to be the smallest integer n such that no matter how all subsets an n-element set are colored with k colors, there is a monochromatic copy of a Berge-G hypergraph.
 It is convenient to define dual functions:  f(n, (G)), the smallest number of colors in a coloring of 2^[n] such that there is no monochromatic Berge-G hypergraph and  f_r(n, (G)), the smallest number of colors in a coloring of [n]r such that there is no monochromatic Berge-G hypergraph.




For G=C_t, the cycle on t vertices,  and r=3, this problem has been already investigated.  It was proved by Gyárfás,  Lehel, Sárközy, and  Schelp <cit.> that R_3((C_t),2)=t for t≥ 5. The fact that  R_3((C_t),3)∼5t 4 was the main result of the paper by Gyárfás and  Sárközy, <cit.>.


The Ramsey problem is closely related to Turán problems. For a family  of hypergraphs,  the Turán number ex_r(n, ) is the largest number of edges in an r-uniform hypergraph on n vertices that does not contain any member from the family  as a subhypergraph.  Indeed, let N=R_r(, k) -1.  Since in a coloring of K_N^r in k colors with no monochromatic member of  each color class has at most  ex_r(N, ) edges, we have

    Nr≤ k · ex_r(N, ).


Note that this inequality gives easy upper bounds on N  if ex_r(N, ) = o(N^r). Győri <cit.> proved that  ex_3(n, (K_3))≤ n^2/8 and the bound is tight. The non-uniform and multi-hypergraph case was addressed in that paper too.  Other results on extremal numbers for Berge hypergraphs were provided by Gerbner and Palmer <cit.>,

 Gerbner, Methuku, and Vizer, <cit.>, Gerbner, Methuku, and Palmer, <cit.>,

as well as by Palmer,  Tait, Timmons, and Wagner <cit.>, and by Grósz, Methuku, and Tompkins <cit.>.



We provide bounds on  uniform and non-uniform Ramsey numbers for Berge-K_3 hypergraphs, including several exact results.  We also give results for Ramsey numbers of Berge hypergraphs for  general graphs.


 Let =(K_3). Then for n≥ 3


  * k/2 - o(k)  ≤ R_3(), k) ≤  3k/4+ o(k),

  *  R_3(,2)=R_3(,3)=5, R_3(,4)=6, R_3(,5)=7, 
  R_3(,6)=8,  R_3(,8)=9,

  * 2^n-2(1-o(1))  ≤ f(n, )≤ 2^n-2,

  *  f(n, )= 2^n-2, for odd n≥ 3, except for n=5. 





We make a connection between r-uniform Ramsey numbers of Berge-G hypergraphs, r≥ 3,  and multicolor Ramsey numbers for auxiliary families of graphs.
For a graph G=(V,E) and v∈ V,  ^*(v) is defined as the class of  all graphs obtained from G  by the following procedure. Let N(v)={q_1,…,q_t} denote the set of vertices adjacent to v in G. Let G'=G-v be the graph obtained from G by deleting v and the edges of G incident to v.  Then, for every q_i∈ N(v)  add a new edge q_ir_i (not in G') where r_i can be any vertex of G' or any new vertex (not in G').
These |N(v)| new edges could be pendant, forming a matching, or could share endpoints. Thus ^*(v) includes G and many other graphs. The graph obtained this way is denoted by G”(v;q_1r_1,…,q_tr_t) and is called an extension of G-v.
 For example, if  G= K_4-e, the graph obtained from K_4 by deleting an edge,  and v is a vertex of degree three in it, ^*(v) consists of G and four other graphs. When G=K_4, ^*(v) consists of G, K_4-e with a pendant edge incident to a vertex of degree 2 of K_4-e, and a triangle with three pendant edges. See
 Figure <ref>.







For any graph G, v∈ V(G), and any integer r≥ 3,  we have R_r((G),k)≤ R(^*(v), k)+r-2.




Consider a k-coloring c of  K=K_n^r on a vertex set V,  |V|=n ≥  R(G^*(v), k)+r-2.
Fix an arbitrary (r-2)-element subset X⊂ V and k-color the edges of the complete graph K' with vertex set V∖ X by the rule c(xy)=c(X∪{x,y}). From the choice of n, we have a monochromatic, say red copy  G”=G”(v;q_1r_1,…,q_tr_t) of a member of ^*(v) in K'.  We claim that K contains a red member of (G).

To prove the claim, let x∈ X and define the graph F as follows. Let 
    V(F)=V(G”)∪{x}, E(F)=(E(G”)∪_i=1^t xq_i)∖ (∪_i=1^t q_ir_i).

We show that the edges of F can be covered by distinct red edges of K. Indeed,  xq_i∈ (E(F)∖ E(G”)) is covered by {q_i,r_i}∪ X and any edge vw∈ (E(F)∩ E(G”)) is covered by {v,w}∪ X and these sets are red edges of K. Thus the graph obtained from F upon removing those r_i-s that are not in V(G') (they are isolated vertices of F) is isomorphic to G and its edges are covered by distinct red edges of K. This proves the claim and Theorem <ref>. 

Since G∈^*(v) for every v, Theorem <ref> implies

 R_r((G),k)≤ R(G,k)+r-2.


However, a much stronger bound follows from Theorem <ref>.

 Set =∪_v∈ V(G)^*(v). Then R_r((G),k)≤ R(,k)+r-2.



If a graph G can be made acyclic by the removal of a vertex, then  R_r((G),k)≤ 4k|V(G)|+r-2 for every r≥ 3.  

If G-v is acyclic, G'=G-v has an acyclic extension G” obtained by adding a matching q_ir_i from N(v) to new vertices. Clearly |V(G”)|<2|V(G)| and since G” is acyclic and R(G”,k)≤ 2k|V(G”)| (see e.g. <cit.>), Corollary <ref> follows from Theorem <ref>.


For the non-uniform case we have the following bounds.


Let G be a graph with at least two edges. If G≠ 2K_2, then


  *  
    2^n-|V(G)|/|E(G)|-1≤ f(n, (G))≤ 2^n-1.

 

  *   In addition, if G has maximum degree at most 2, then
 
    2^n-1/|E(G)|-1(1-o(1))≤ f(n, (G)).


  *   
    f(n, (2K_2)) = 2^n - n2-n-1.





Moreover, we have some results for Ramsey numbers of (K_4).
Set K_4^*=K_4^*(v), for a vertex v in K_4.

 We have that for a positive constant c



  * 2^ck≤ R_3((K_4), k)≤ R(K_4^*, k)+1≤ e(1+o(1))(k-1)k!,

  * R_3((K_4),2)=6.






Note that part 1 in  Theorem <ref> shows that the upper bound of the multicolor Ramsey number for the family K^*_4(v) differs from the best known upper bound of R(K_3,k) only by a factor  linear in k. It is also worth mentioning that part 2. in Theorem <ref> shows that R_3((K_4),2) is much smaller than its classical counterpart, R_3(K_4^3,2)=13, <cit.>.

The rest of the paper is structured as follows. In Section <ref> we treat the non-uniform case proving parts 3 and 4 of Theorem <ref> and Theorem <ref>.  In Section <ref> we prove the remaining parts 1 and 2 of Theorem <ref>.
Finally, in Section <ref> we prove Theorem <ref>.











































§ THE NON-UNIFORM CASE

















Proof of Theorem <ref>/1 - upper bound. If G is not a 2K_2, make each color class consisting of a set and its complement. This gives a general upper bound.

Proof of Theorem <ref>/3 - upper bound. For the upper bound on f(n, (K_3)), consider the coloring of 2^[n] such that each color class consists of four sets:   A,  [n-1]-A, [n]-A, and A∪{n} for A⊆ [n-1]. Then the total number of colors is 2^n-2. The four sets of each color class do not contain Berge-K_3.

Proof of Theorem <ref>/1 - lower bound. To prove the bound f(n, (G))≥2^n-|V(G)|/|E(G)|-1, consider a set S of |V(G)| vertices and the set  of  all subsets containing S.
Note that any |E(G)| sets from   form a Berge-G hypergraph.
Thus there are at most |E(G)|-1 members of  of each color.
Therefore the total number of colors is at least the number of colors used on , that in turn is at least

    ||/|E(G)|-1 = 2^n-|S|/|E(G)|-1 = 2^n- |V(G)|/|E(G)|-1.


Proof of Theorem <ref>/2.
Let  G be a graph with maximum degree at most 2.
Consider , the set of all subsets of [n] of size at least n+|V(G)| 2. Then any two sets from  intersect in at least |V(G)| elements.
We claim that any |E(G)| sets from  form a Berge-G graph.
Assume that G is a cycle on k vertices, for other graphs of maximum degree at most 2, the argument is similar.
Consider an arbitrary family   X_1, …, X_k of sets from .
Pick  vertices  x_1∈ X_1∩ X_2,  x_2∈ (X_2∩ X_3) ∖{x_1}, and so on, x_i∈ (X_i∩ X_i+1)∖{x_1, …, x_i-1}, i=2, …, k-1.
Finally pick x_k ∈ (X_k∩ X_1) ∖{x_1, …, x_k-1}. Since pairwise intersections have size at least k, it is always possible to make such a choice of x_1, …, x_k.
Then {x_1, …, x_k} forms an underlying  vertex set of a  Berge-C_k.

Thus in a coloring of  with no monochromatic Berge-G, there are at most |E(G)|-1 sets of the same color. This implies that the number of colors is at least

    ||/|E(G)|-1≥2^n-1 - c|V(G)| 2^n/√(n)/|E(G)|-1≥2^n-1/|E(G)|-1 - o(2^n).

Proof of Theorem <ref>/3 - lower bound. The lower bound for Berge-K_3 follows from the previous proof.

Proof of Theorem <ref>/4. When n is odd, consider all sets of size at least (n+1)/2. We claim that any three of those, say A_1,A_2,A_3, form a Berge-K_3
hypergraph. Indeed, the three sets A_i∩ A_j (1≤ i<j≤ 3) have distinct representatives by checking Hall's condition. It is obvious that none of them is empty and the union of any two of them has at least two elements. Moreover, their union has at least three elements except for n=5 (when three sets of size three can intersect in two elements).


Thus in any coloring of 2^[n] with no monochromatic copy of Berge-K_3 hypergraph, there are at most two subsets of size at least (n+1)/2 that have the same color. Thus the total number of colors in such a coloring is at least
|{A:   |A|≥ (n+1)/2, A ⊆ [n]}|/2 = 2^n-2. The upper bound follows from Theorem <ref>/1.

Proof of Theorem <ref>/3. To  prove that f(n,(2K_2)) = 2^n - n2-n-1,  note that in any coloring of subsets of size at least three in [n] without monochromatic (2K_2), all subsets must have distinct colors. Thus  
    f(n,(2K_2)) ≥ |{X: X⊆ [n], |X|≥ 3}| =
    2^n - n2 -n -1.
  On the other hand, the following coloring has no monochromatic (2K_2):
color all sets of size at least 3 with distinct colors, color each set of at most two elements with the color of some 3-element set containing it. Then each color class of size at least two consists of subsets of some three element set, so it does not contain a copy of (2K_2) and the number of colors is 2^n - n2 - n -1.














§ RAMSEY NUMBER OF THE BERGE TRIANGLE

In this subsection we set =(K_3).

Proof of Theorem <ref>/1,2 - upper bounds.







Consider a coloring of K_n^r, an r-uniform n-clique with k colors without monochromatic member of , n= R_r(, k)-1.
Then each color class has at most ex_r(n, ) edges. A result of Győri <cit.> implies that  ex_r(n, )≤n^2/8(r-2).
Thus nr,   the total number of hyperedges,  is at most k n^2/(8(r-2)).
This provides the general upper bounds  and all upper bounds for the Ramsey numbers for i colors, i=2,3,4,5,6,7,8. 


Proof of Theorem <ref>/1 - lower bound.
We shall instead provide an upper bound on the number of colors needed to color the triples on n vertices so that no monochromatic Berge-K_3 is created.
We split the vertex set in two almost equal parts, A and B.
Let A_1, A_2,  … and B_1, B_2 …
be color classes of optimal  proper  edge-colorings of  complete graphs (uniformity 2) on a  vertex set A and on a vertex set B, respectively.
Let _i = {{x,y,z}:  {x,y}∈ A_i, z∈ B}, let _i =  {{x,y,z}:  {x,y}∈ B_i, z∈ A}.
Then we see that each of _i's and _i's does not contain a member or . Moreover these classes of triples contain all hyperedges of K_n^3 with vertices in both A and B. Color all triples in _i with color a_i, all tripes in _i with color b_i, for distinct a_i's and b_i's.
Further, color the triples with all elements in A or with all elements in B recursively using new colors such that the set of colors used on triples from A is the same as the set of colors used on triples from B.
Let f(n) be the number of colors given by this construction and χ'(G) denote the chromatic index of a graph G.
Then

    f(n)    ≤   χ'(K_⌊ n/2 ⌋) + χ'(K_⌈ n/2 ⌉) + f(⌈ n/2 ⌉)
       ≤   ⌊ n/2 ⌋+ ⌈ n/2 ⌉+ f(⌈ n/2 ⌉)
       =     n+ f(⌈ n/2 ⌉)
       ≤    2n + log n.


So, we have that the number of colors k is bounded as k≤ 2n + log n,
thus n≥ k/2 - o(k).

Proof of  Theorem <ref>/2 - lower bounds.
The lower bound for 2 and 3 colors is obvious since  two edges of K_4^3 can be colored red and  the other two  blue. An
-free 4-coloring of K_5^3 on [5] can be  given by splitting the edge set into color classes as follows:

    123,124,125;  134,234,345; 135,145;  235,245.

Note that for each color class there is a pair of vertices that belongs to each hyperedge of this class, thus there is no monochromatic  Berge-K_3 hypergraph.
An -free 5-coloring of K_6^3 on [5]∪∞ can be  given so that the first color class is 
    ∞12,∞13,345,245
 and each other color class is obtained from the first one by cyclically shifting the vertex labels that are not ∞  and keeping ∞ fixed.  Finally, an -free 6-coloring of K_7^3 on [5]∪∞_1 ∪∞_2 can given so that the first color class consists of 5 edges:
∞_1∞_21,  ∞_1∞_2 2, ∞_1∞_23, ∞_1∞_2 4, ∞_1∞_2 5.
The second color class is  
    125,134,∞_125,∞_225,∞_134,∞_234,
  and third  through sixth color classes are obtained from the second by  keeping ∞_1,∞_2 fixed and cyclically shifting other vertex labels.
The lower bound for 8 colors comes from the general construction.





















































§ RAMSEY RESULTS FOR BERGE-K_4


In this section, set =(K_4).

Proof of Theorem <ref>/1 - lower bound.
A natural lower bound on R_3(,k) comes from covering the edges of K_n^3 with the smallest possible number of 3-partite subhypergraphs. Indeed, a 3-partite 3-uniform hypergraph cannot contain any member of , thus f(n), the minimum number of 3-partite hypergraphs needed to cover all edges of K_n^3 provides a coloring with f(n) colors containing no monochromatic member from .  This is a well studied problem in coding theory, a special perfect hash family.  Apart from very small n, exact values of f(n) are not known, only upper bound tables are available <cit.>. The order of magnitude of f(n) is known, c_1log(n)≤ f(n)≤ c_2log(n) <cit.>. The upper bound implies
that  2^ck≤ R_3(,k) for a positive constant c.



Interestingly, the upper bound of f(n) is easy from probabilistic constructions, however, simple explicit constructions are not known (for general n). It seems worthwhile to give a very simple construction leading to a 2log_2^2(n) upper bound.




Split the vertex set of K_n^3 into two almost equal parts A and B,
  consider colorings c_A,c_B on the pairs of A,B with no monochromatic K_3 and with disjoint color sets. Extend this coloring to edges of K_n^3 intersecting both A and B as follows: edges xyz with x,y∈ A,z∈ B are colored with c_A(xy), edges xyz with x∈ A,y,z∈ B are colored with c_B(yz).  This can be easily done by using  no more than 2log_2(n) colors. The uncolored edges, i.e. edges inside A and inside B can be colored recursively, using the same set of new colors. This leads to the recursive bound f(n)≤ 2log_2(n)+f(⌈ n/2 ⌉).





Proof of Theorem <ref>/1 - upper bound.
The inequality   R_3(, k)≤   R(K_4^*(v), k) follows from Theorem <ref>. Thus Theorem <ref> follows from the following lemma.

 For any  ϵ,  0<ϵ<1/4, and any k≥ 1,
R(K_4^*(v), k)≤ (1+ϵ)^k ϵ^-1  k!.
In particular,   R(K_4^*(v), k)≤ (k-1)e(1+o(1))k!.




We shall prove the statement by induction on k with a trivial basis for k=1.
Consider a coloring of E(K_n),  with k colors and no monochromatic copy of a member from K_4^*(v). Note that from each monochromatic triangle T of a fixed color class i we can select one  vertex v_i(T) of degree two in color class i. Let X_i=∪ v_i(T), where the union is taken  over all monochromatic triangles of color i.
Then X_i  is an independent set in color i, i.e. cannot contain any edge of color i.  By induction
|X_i| ≤ (1+ϵ)^k-1ϵ^-1 (k-1)!.


Case 1. |X_i|> n/((1+ϵ)k) for some i.   

Then n≤ (1+ϵ) k |X_i|≤  (1+ϵ)k  (1+ϵ)^k-1ϵ^-1 (k-1)! = (1+ϵ)^k ϵ^-1 k! by induction.


Case 2.  |X_i|≤ n/ ((1+ϵ) k) for each i.
Note that deleting all X_i's leaves vertex set X' of size at least n- n/(1+ϵ) = n ϵ /( 1+ ϵ) such that X' does not contain any monochromatic triangles. Then n≤ (1+ϵ) |X'| /ϵ≤ (1+ ϵ) R(K_3, k) /ϵ≤ k! (1+ϵ)/ϵ≤ (1+ϵ)^k ϵ^-1 k!.



Optimizing over ϵ, for large k we see that for ϵ = 1/(k-1), n ≤ (k-1)e(1+o(1))k!.



Proof of Theorem <ref>/2.  Note that Theorem <ref> gives

    R_3(,2)≤ R(K_4^*(v),2)+1

and the Ramsey number on the right can be determined easily.

  R(K_4^*(v),2)=7.


Set =(K_4^*(v)). For the lower bound R(,2)≥ 7, consider K_3,3 and its complement as a 2-coloring on K_6.


For the upper bound, suppose  K=K_7 is colored with red and blue.  A well-known result of Goodman <cit.> implies that any 2-colored K_7 contains at least four monochromatic triangles, among them two of the same color, say T_1,T_2 are vertex sets of  red triangles.

Suppose for contradiction that we have no monochromatic member of .  This implies that there exist v_1∈ T_1,v_2∈ T_2 with red degree two in K. Consequently the edge v_1v_2 and all edges incident to v_1,v_2 and not on T_1,T_2 are blue. Set

    T=(T_1∪ T_2)∖{v_1,v_2},  S=V(K)∖ (T_1∪ T_2).
 Easy inspection shows that either there is a blue member of  with base triangle v_1,v_2,s with s∈ S or all edges of [S,T] are red. In the latter case any red triangle with a red edge in T^* and with any s∈ S is a base triangle of a red member of , apart from one case: when |S|=3, |T|=2. In this exceptional case a red edge s_1s_2  gives a red member of  (with base triangle s_1∪ T) and a blue edge s_1s_2 gives a blue member of  (with base triangle s_1s_2v_1).


Unfortunately,  Lemma <ref> implies through (<ref>) only R_3(,2)≤ 8, to decrease it by two seems to require more difficult argument.
First we need the Turán number of  for n=5.



 ex_3(5, )=5.

 Five edges clearly do not form  thus we have to show ex_3(5,)< 6. Assume H is a 3-uniform hypergraph with six edges on a vertex set [5] without any member of . Observe that the maximum vertex degree of H is at least ⌈6× 3 5⌉=4.


  * Suppose that for some 1≤ i<j≤ 5, ij is not covered by any edge of H. By symmetry, let i=1,j=2. Then H either contains the six edges meeting {1,2} in one vertex or one of them, say 234 is missing. In the first case the assignment 
    e_13=134,e_14=145,e_15=135,e_34=234,e_35=235,e_45=245
 defines a , otherwise the assignment e_34=234 is replaced by the assignment e_34=345 to get a . In both cases we have a contradiction. Thus all pairs of vertices are covered by some edge of H. Assume that vertex 1 has maximum degree in H.


  * If d(1)=6 then the edges containing 1 can be obviously assigned to pairs of {2,3,4,5} to form a member of . Similarly, if d(1)=5 then the five edges containing 1 with the edge covering the  yet uncovered pair of the link of 1 form a member of  on {2,3,4,5}. Both cases yield contradiction.


  * If d(1)=4 then the link of 1 is either the four cycle 2,3,4,5,2 or the graph with edges 23,34,24,45. In the first case we have a member of  on {2,3,4,5} with the assignment 
    e_23=123,e_34=134,e_45=145,e_25=125

    extended by the edges covering the uncovered pairs 24,35. In the second case we make the assignments 
    e_23=123,e_24=124,e_34=134,e_45=145.
 If there exist two distinct edges of H to cover the yet uncovered pairs 25,35 we get a member of  on vertex set {2,3,4,5}.  Otherwise 234,235 are both edges of H and we have a member of  on {1,2,3,4} by the assignments 
    e_12=123,e_13=134,e_14=145,e_23=235,e_24=124,e_34=234,

    a contradiction, finishing the proof. 






We are ready to prove that R_3(, 2)=6.   It is easy to see that R_3(,2)≥ 6 since in any 2-coloring of K_5^3 with five edges in each  color class there is no monochromatic member of .

For the upper bound consider a 2-coloring c of the edges of K=K_6^3 with no monochromatic member of .  Let H be the hypergraph defined by the edges of the majority color, containing at least 10 hyperedges. By Lemma <ref>, any 5 vertices of H induce at most 5 hyperedges, thus the remaining at least |E(H)|-5
hyperedges contain the sixth vertex, i.e., d(v)≥ |E(H)|-5 for every v∈ V(H) implying

    6(|E(H)|-5)≤∑_v∈ v(H) d(v)=3|E(H)|,

that in turn implies that  |E(H)|≤ 10. On the other hand |E(H)|≥ 10, thus |E(H)|=10 and so the inequality in (<ref>) hold as equality. In particular, H is 5-regular, implying the same for the other color. Thus we may assume that K is partitioned into a red and a blue hypergraph H_r,H_b both 5-regular.

Let v be an arbitrary vertex of H and consider the hypergraphs induced by H_r,H_b on V-v=[5]. By Lemma <ref> both contain (K_4-e), we show that some of them can be extended to  by adding a suitable edge of K containing v. It is convenient to represent H_r, H_b with the graphs G_r, G_b of their complements (with their inherited colorings).  Apart from color changes we have four possible cases.

Case 1.  G_r,G_b are complementary five cycles. Assume the edges of G_r are i,i+1, thus  edges i,i+1,i+2 belong to H_r.  Every four element subset form a (K_4-e) in H_r, for example the edges 
    e_12=123,e_45=145,e_25=125,e_24=234,e_35=345
 cover all pairs of {2,3,4,5} except {3,4}. Thus we have a red  unless {v,i,i+1} are all forming blue edges in K. The same argument gives that {v,i,i+2} must be red edges of K. But then there are many monochromatic s, for example the assignment 
    e_12=123,e_45=145,e_25=125,e_24=v24,e_35=v35, e_45=345
 gives one on {2,3,4,5}.

Case 2.  G_r,G_b are complementary bulls.  Assume that the edges of G_r are 12,23,34,24,45, implying that the edges 345,123,145,125,135 belong to of H_r and the edges  234,235,134,245,124 belong to H_b.  Then we have two (K_4-e)s in H_r on {1,2,3,5}. One of them with 
    e_12=123,e_13=135,e_15=145,e_25=125,e_35=135
 implying that v23 must be blue. The other is  
    e_13=135,e_15=145,e_23=123,e_25=125,e_35=135

implying that v12 must be blue. However, then vertex 2 has degree at least six in H_b, contradiction.

Case 3.  G_r=K_4-e, G_b is its complement.  Assume that the edges of G_r are 12,23,34,14,24, then edges 125,135,145,235,345 belong to H_r and  edges 123,124,134,234,245 belong to H_b. We have three (K_4-e)s in H_b on vertices {1,2,3,4}. All use assignments 
    e_23=234,e_24=245,e_34=134
 and they can be extended to (K_4-e) with e_13=123,e_14=124,  or e_12=123,e_14=124 or e_12=124,e_13=123,  respectively. Since we have no (K_4) in H_b, the edges 12v,13v,14v are all red and vertex 1 has degree at least six in H_r, contradiction.

Case 4.  G_r is a four-cycle with a pendant edge, G_b is its complement.  Assume that the edges of G_r are 12,23,34,45,25, then edges 123,125,145,134,345 belong to H_r and  edges 124,135,234,235,245 belong to H_b. Then we have two (K_4-e)s in H_b on {1,3,4,5}. We can assign in both 
    e_14=124,e_34=234,e_35=235,e_45=245
 and complete it with either e_13=135 or e_15=135. Since we have no (K_4) in H_b, 13v,15v are both red edges, consequently vertex 1 has degree at least six in H_r, contradiction.














 99






CW C. J. Colbourn, R. A. Walker II, Perfect hash families: constructions and existence, Journal of Mathematical Cryptology 1 (2007) 125-150.

FK M. L. Fredman, J. Komlós, On the size of separating systems and families of perfect hash functions, SIAM Journal of on Algebraic and Discrete Methods 5 (1984) 61-68.

GMV D. Gerbner, A. Methuku, M. Vizer, Asymptotics for the Turán number of Berge-K_2,t, (2017) arXiv:1705.04134v2

GMP D. Gerbner, A. Methuku,  C. Palmer, A general lemma for Berge-Turán problem, manuscript.


GP  D. Gerbner, C. Palmer, Extremal results for Berge-hypergraphs, SIAM Journal on Discrete Mathematics,  (2015) 31(4): 2314–2327.

GO A. W. Goodman, On sets of acquaintances and starangers at any party, American Mathematical Monthly 66 (1959) 778-783.

GMT D. Grósz,  A. Methuku,  C. Tompkins, Uniformity thresholds for the asymptotic size of extremal Berge-F-free hypergraphs, (2018) arXiv:1803.01953v1

GYLSS A. Gyárfás, J. Lehel, G. N. Sárközy, R. H. Schelp, Monochromatic Hamiltonian Berge cycles in colored complete uniform hypergraphs, Journal of Combinatorial Theory B. 98 (2008) 342-358.

GYS A. Gyárfás, G. N. Sárközy, The 3-colour Ramsey number of a 3-uniform Berge cycle, Combinatorics, Probability and Computing 20 (2011) 53-71.

G E.  Győri, Triangle-free hypergraphs.  Combinatorics, Probability and Computing 15 (2006), 185–191.

GRS R. L. Graham, B. L. Rothschild, J. H. Spencer, Ramsey Theory, Wiley, New York (1990)

PTTW C. Palmer,  M. Tait, C. Timmons,  A. Z. Wagner, Turán numbers for Berge-hypergraphs and related extremal problems (2017) arXiv:1706.04249v1

RAD S. P. Radziszowski, Small Ramsey numbers,
Electronic Journal of Combinatorics, (2017), DS1.15.


