A proof of a conjecture of Erdős and Gyárfás on monochromatic path covers
Alexey Pokrovskiy Leo Versteegen Ella Williams






                        

                        

8in       
                        
6.6in        


margin = 2.4cm


















theoremTheorem[section]
definition[theorem]Definition
proposition[theorem]Proposition
example[theorem]Example
conjecture[theorem]Conjecture
lemma[theorem]Lemma
corollary[theorem]Corollary
observation[theorem]Observation
*remarks*Remarks
*remark*Remark
claim[theorem]Claim
equation
item
equationsection
proofclaim[1][Proof of claim]

⌈⌉







#1
	
 
ε



















A proof of a conjecture of Erdős and Gyárfás on monochromatic path covers
    Alexey PokrovskiyDepartment of Mathematics, University College London, Gower Street, WC1E 6BT, UK. Emails:  Leo Versteegen[1] Ella Williams[1]
    
==================================================================================================================================================




§ ABSTRACT 
In 1995, Erdős and Gyárfás proved that in every 2-edge-coloured complete graph on n vertices, there exists a collection of 2√(n) monochromatic paths, all of the same colour, which cover the entire vertex set. They conjectured that it is possible to replace 2√(n) by √(n). We prove this to be true for all sufficiently large n.





§ INTRODUCTION


In <cit.>, Gerencsér and Gyárfás observed the following fact with a very short and elegant proof.


    The vertex set of any 2-edge-coloured complete graph K_n can be covered by two monochromatic paths.


Importantly, the two monochromatic paths do not have to be of the same colour. In his survey <cit.>, Gyárfás mentions that when he first told Erdős about this result, Erdős misunderstood this detail, which led the two of them to investigate the smallest number of monochromatic paths of the same colour that cover all vertices of a 2-edge-coloured complete graph. In <cit.>, they proved the following.


    In every 2-edge-coloured complete graph on n vertices, there exists a collection of 2√(n) monochromatic paths, all of the same colour, which cover the entire vertex set.


The bound 2√(n) in <Ref> is best possible up to a constant by the following construction. Suppose √(n)∈ℕ and partition V(K_n) into disjoint sets A and B of order n-√(n)+1 and √(n)-1 respectively. Colour the edges contained in A blue, and all other edges red. Each red path covers at most √(n) vertices in A since it must alternate between A and B, so we need at least ⌈ |A|/√(n)⌉ = √(n) red paths to cover the entirety of V(K_n). Every collection of blue paths covering V(K_n) must include all individual vertices in B as distinct paths and needs another blue path to cover A, thus has size at least |B|+1 = √(n). If n is not a perfect square, one can use the same construction with | B|=⌊√(n)⌋-1, so that any cover requires at least ⌊√(n)⌋ paths of the same colour.

Erdős and Gyárfás conjectured (see <cit.>) that this construction is the colouring that requires the most paths for a cover, meaning that the bound in their theorem could be improved to √(n). In this paper, we confirm their conjecture for all sufficiently large n.


There exists n_0∈ such that for all n>n_0 and all 2-edge-colourings of E(K_n), there exists a collection of at most √(n) monochromatic paths of the same colour that cover the vertices of K_n.


The constant n_0 that we find is large, but with some additional technical effort, one can show that for all n∈, √(n)+10 monochromatic paths of the same colour are sufficient to cover K_n. 

Several related problems of this type have also been studied, looking for monochromatic structures that either cover or partition the vertex set within an edge-coloured graph. 

For example, Lehel's conjecture, proven in full by Bessy and Thomassé <cit.>, strengthens <Ref>. It states that the vertices of a 2-edge-coloured K_n can be covered by two vertex-disjoint monochromatic cycles (of course, they must be allowed to have different colours). A famous generalisation of Lehel's conjecture due to Gyárfás <cit.>, stating that an r-edge-coloured complete graph can be covered by r monochromatic cycles, remains wide open. We refer the reader to the survey <cit.> for partial results and further related problems. 

Finally, as an interpolation between <Ref> and <Ref>, Eugster and Mousset <cit.> investigated the minimal number of monochromatic paths needed to cover the r-edge-coloured K_n if at most s≤ r different colours are allowed to be used for the paths in total.



§ PRELIMINARIES

 We call a collection 𝒫 of paths in a red-blue edge-coloured graph G a red path cover if every vertex in V(G) is covered by some path in 𝒫, and every P ∈𝒫 contains only red edges. We define a blue path cover similarly. 
 The length of a path is the number of edges it contains, and importantly we allow paths to have length zero, so that a path can be a single vertex. 
 Note that paths need not be disjoint, unlike those required for some definitions of the path covering number of a graph.

We will use a bipartite Ramsey-type result for paths determined by Gyárfás and Lehel in <cit.> (see Theorem 3 and Remark 1).

    If k and ℓ are distinct natural numbers then every red-blue edge-coloured complete bipartite graph K_⌈k+l/2⌉,⌈k+l/2⌉ contains a red path of length k or a blue path of length ℓ. 





Suppose we have found a long monochromatic path P in a red-blue edge-coloured K_n, without loss of generality we may assume P is blue. 
We may consider the bipartite graph between V(P) and a subset of V(K_n) ∖ V(P), comprised only of red edges. If there is a long red path, say R, is this bipartition then we obtain a large set V(P)∩ V(R) covered by both a red path and a blue path, which allows us some flexibility for covering the remainder of the vertices. 
A similar idea may be used if we can find few red paths that cover many vertices in the bipartition. In the following two lemmas we consider certain degree properties within bipartite graphs that allow us to find few paths covering many vertices.


Let G be a bipartite graph on vertex set X∪ Y with the property that every vertex in Y has degree at least (| X| +| Y|)/2. Then G contains a path covering 2| Y| vertices.


    Let P=x_1y_1… x_ky_k be a path starting in X and ending in Y and suppose that k<| Y|. Fix y_k+1∈ Y∖{y_1,…,y_k}. We have
    
    | N(y_k)∩ N(y_k+1)|≥| X| +| Y|/2-(| X| -| X|+ | Y|/2)=| Y|>k.

    Therefore, y_k and y_k+1 have a common neighbour x_k+1∈ X∖{x_1,…,x_k}, and we can extend P via y_kx_k+1y_k+1.



Let m∈ and let G be a bipartite graph on vertex set X∪ Y with  | X|≥| Y|+2m, and such that every vertex in Y has degree at least | X| -m. Then G contains a collection of at most ⌊| X| /| Y|⌋ paths whose union covers all but | Y| + 2m vertices in X and all vertices in Y.


    We prove the statement by induction on |X|, always assuming that | X|≥| Y | + 2m. Since
    
    | X| -m ≥| X|+| Y|/2,

    we may apply <Ref>, to obtain a path P covering 2| Y| vertices in G. In particular, P covers all vertices in Y. Let X'=X∖ V(P), and note that in the induced subgraph G'=G[X'∪ Y], every vertex in Y has degree at least | X'|-m. If | X'|≤| Y|+2m, then {P} is a collection of paths as desired. Otherwise, we may apply the induction hypothesis to G[X'∪ Y] to obtain a collection of paths P_1,…,P_k with k≤⌊| X'| /| Y|⌋=⌊| X| /| Y|⌋-1 that cover all but | Y| +2m vertices in X'. Adding P to this collection yields the claim.


To get the exact bound in <Ref>, we also require a version of <Ref> which lets us cover all vertices in X when many vertices in Y are adjacent to all vertices in X.


Let G be a non-empty bipartite graph on vertex set X∪ Y with sets X_0={x∈ X: d(x)=| Y|}, X_1=X∖ X_0, Y_0={y∈ Y:d(y)=| X|}, and Y_1=Y∖ Y_0 such that

    
  * | X|> | Y|, and
    
  * X_1=Y_1=∅ or | X_0|/| Y_1|>2| X_1| /| Y_0|.

Then G contains a collection of at most ⌈| X|/| Y| +1⌉ paths that cover all vertices in G.


    We prove the statement again by induction on |X|. It follows from (i) and (ii) that | X_0|≥| Y_1|+1, and therefore, G contains a path P with 2| Y_1|+1 vertices, alternating between X_0 and Y_1, such that P starts at x_0 ∈ X_0 and also ends in X_0. In particular P covers all vertices in Y_1. 
    
    Furthermore, since every vertex in Y_0 has neighbourhood X, and | X| > | Y|, G contains a path Q with 2min{| Y_0|, | X_1|} vertices, alternating between Y_0 and X∖ V(P), that starts at y_0∈ Y_0 and covers min{| Y_0|, | X_1|} vertices in X_1. Consider the concatenated path R=Px_0y_0Q and the graph G'=G[X'∪ Y] where X'=X∖ V(R). 

    Defining the sets X_0',X_1',Y_0', and Y_1' analogously for G' to X_0,X_1,Y_0, and Y_1 were defined for G respectively, we observe that Y_1'⊂ Y_1 and X_1'⊂ X_1∖ V(Q), while Y_0⊂ Y_0'. If we assume that X_1'=∅ or Y_1'=∅, then it follows that G' is complete bipartite and it is trivially possible to cover X∖ V(R) with ⌈| X'|/| Y| +1⌉ =⌈| X|/| Y| +1⌉-1 paths so that nothing is left to show. Suppose therefore that X_1,Y_1≠∅, in particular, we must have | X_1| >| Y_0| so that | V(Q)∩ X_1| =| Y_0|. Using this, we see that

    
    | X_0'|/| Y_1'|≥| X_0∖ V(P)|/| Y_1|≥| X_0|/| Y_1|-2>2(| X_1|/| Y_0| - 1 )= 2| X_1∖ V(Q)|/| Y_0|>2| X_1'|/| Y_0'|.


    If | X'|> | Y'|, we may use the induction hypothesis to obtain a family 𝒫 of at most ⌈| X|/| Y| +1⌉-1 paths which cover all of X' and Y, and together with R, these paths cover all of G. 
    
    If | X'|≤| Y'| on the other hand, then we must have | Y_0'| >| X_1'| so that it is possible to cover all of X_1' with a single path Q' of length 2| X_1'|. The remaining graph G'-V(Q') is complete bipartite so that we may find a path P' that covers all of X_0' in it. Concatenating P' and Q' suitably, we obtain a second path R' such that R and R' cover all of G.




§ PROOF OF <REF>


Let n ∈. In what follows, without loss of generality we assume the vertex set of K_n is given by [n]. Let _n be the set of all red-blue colourings of E(K_n). For χ∈_n, denote by f(n,χ) the smallest family of monochromatic paths of the same colour that cover [n]. Furthermore, let f(n)=max_χ∈_n f(n,χ).


In order to prove <ref>, we follow an inductive strategy to initially prove a weaker upper bound on f(n) for all n ∈, given in <ref> which can then be bootstrapped to prove our main theorem. Thus in each of the lemmas in this section, we will assume an upper bound on f(m) for all m<n that will relate to our inductive hypothesis.

We first introduce a lemma which tells us that under a colouring χ∈_n, if there exists a large set S that is covered by both a collection of few red paths, and a collection of few blue paths, then we can obtain a strong upper bound on f(n,χ).


Let C_1≥ C_2≥ 0 and let n∈ be such that f(m)<√(m)+C_1 for all m<n. Let further k∈ and χ∈_n be such that there exist red paths P_1,…, P_k⊂ K_n, blue paths Q_1,…,Q_k⊂ K_n, and a set S⊂ [n] satisfying S⊂ (V(P_1)∪…∪ V(P_k))∩ (V(Q_1)∪…∪ V(Q_k)). If

    √(n-| S|)+C_1+k≤√(n)+C_2,

then f(n,χ)≤√(n)+C_2. In particular, if there is a red path P and a blue path Q such that S⊂ V(P)∩ V(Q), and

    | S|≥ 2(C_1-C_2+1)√(n),

then f(n,χ)≤√(n)+C_2.



Suppose there exist red paths P_1,…, P_k⊂ K_n, blue paths Q_1,…,Q_k⊂ K_n, and a set S⊂ [n] satisfying  S⊂ (V(P_1)∪…∪ V(P_k))∩ (V(Q_1)∪…∪ V(Q_k)).
Let H be the 2-edge-coloured graph obtained by deleting S from K_n under the colouring χ. Then H has m=n-|S| vertices, and by definition of f(m), there exists a collection of at most f(m) monochromatic paths of the same colour which cover V(H). Adding {P_1,…,P_k} or  {Q_1,…,Q_k} to this collection according to whether these paths are red or blue respectively yields a collection of at most f(m)+k monochromatic paths of the same colour covering V(H) ∪ S = [n] in K_n. By our assumptions, we have 

    f(n,χ) ≤ f(m) + k < √(m) + C_1 +k = √(n-| S|)+C_1+k≤√(n)+C_2,

as desired. 
For the second part of the statement, observe that if there is a red path P and a blue path Q such that S⊂ V(P)∩ V(Q) for some S ⊂ [n] with | S|≥ 2(C_1-C_2+1)√(n), then

    √(n-|S|)≤√(n-2(C_1 -C_2+1))≤√(n) - (C_1 -C_2+1).

Rearranging gives 

    √(n-| S|)+C_1+1≤√(n)+C_2,

and so taking k=1, we deduce that f(n,χ)≤√(n)+C_2.


We now show that if χ∈_n is such that there exists no small monochromatic path cover, then there must exist some long monochromatic path, of colour γ say, such that for every vertex y outside of the path, there are few vertices x on the path such that χ(xy)=γ.


Let C_1≥ C_2≥ 0 and let n>8^4(C_1-C_2+1)^4 be such that f(m)<√(m)+C_1 for all m<n. If χ∈_n is such that f(n,χ)>√(n)+C_2, then there a monochromatic path P such that the size of Y= [n]∖ V(P) is at most √(n)+8(C_1-C_2+1)√(n). Furthermore, if γ is the colour of the edges of P, then for every y∈ Y, the size of {x∈ V(P): χ(xy)=γ} is at most 2(C_1-C_2+1)√(n).



Let Δ = C_1-C_2 and let χ∈_n be such that f(n,χ)>√(n)+C_2. Without loss of generality, there exists a blue path Q which covers ⌊ n/2⌋ vertices. Let W be a subset of [n]∖ V(Q) of size ⌊ n/2⌋ and consider the longest red path R in the complete bipartite graph between V(Q) and W. The set V(R)∩ V(Q) is covered both by a single red and a single blue path so that by <Ref>, we may assume that | V(R)∩ V(Q)|<2(Δ+1)√(n). However, since R is a path in a bipartite graph between V(Q) and W, at least ⌊| V(R)| /2⌋ vertices of R must lie in V(Q), and thus, it follows that | V(R)|<4(Δ + 1)√(n). By <Ref>, there exists a blue path of length at least n-2(Δ+1)√(n)-1 between V(Q) and W.

Let P be the longest   blue path in K_n, denote its vertex set by X, and let Y=[n]∖ X. Consider y∈ Y and let B denote the set of blue neighbours of y in P. Since P cannot be extended, B does not contain any endpoint or any two consecutive vertices of P. Furthermore, if we direct P arbitrarily, the predecessors of B form a red clique set. Indeed, if P=v_1v_2… v_k, 1≤ i<j≤ k, and v_iv_j, v_i+1y, and v_j+1y were all blue, then v_1… v_iv_jv_j-1… v_i+1yv_j+1… v_k would be a blue path of length k+1. However, we may argue as before that V(P) cannot contain a red path of length 2(Δ+1)√(n), which means that y has at most 2(Δ+1)√(n) blue neighbours in X.

In other words, taking m=2(Δ+1)√(n), each vertex in Y has at least | X| -m blue neighbours in X. What is more, we know that | X|≥ n-2(Δ+1)√(n)-1 and hence | Y|≤ 2(Δ+1)√(n)+1. Thus, as n>100(Δ+1)^2,

    | X|≥ n-2(Δ+1)√(n)-1 > 10(Δ+1)√(n)-2(Δ+1)√(n)-1>6(Δ+1)√(n)+1≥| Y | + 2m.

It now follows from <Ref> that the bipartite graph given by the red edges between X and Y contains a collection of at most ⌊| X|/| Y|⌋ <n/| Y| paths which cover all but |Y|+ 2m<6(Δ+1)√(n)+1 vertices in X and all vertices of Y.

However, all vertices in X that are covered by this collection of paths are also covered by the single blue path P, which means that by <Ref>,


    √(n)+C_2<√(6(Δ+1)√(n)+1)+C_1 +n/| Y|≤ 3(Δ+1)√(n) +C_1+n/| Y|,


which we can simplify to


    √(n)<n/| Y| + 4(Δ+1)√(n),


which implies that


    | Y | < n/√(n)-4(Δ+1)√(n)=√(n)/1-4(Δ+1)/√(n).


Since we have √(n)≥ 8(Δ+1) by assumption and 1/(1-x)<1+2x for x∈ [0,1/2], we get that


    | Y | < √(n)+8(Δ+1)√(n),


as desired.


If there exists a monochromatic path in K_n containing almost all vertices, we can afford to cover the remaining vertices individually or in pairs. The following lemma formalises this. 


    Let n∈ and χ∈_n and suppose P is a blue path in K_n. Let Y=[n]∖ V(P) and write Y_0 for the set of vertices in Y that are not contained in a blue edge with any vertex in V(P).
    
    Then we have
    
    f(n,χ) ≤ 1+⌈| Y∖ Y_0|/2⌉ + | Y_0| < 2+ | Y|/2 + | Y_0|/2.

    



    Let Y_1 Y∖ Y_0 and note that for any two vertices y_1,y_2∈ Y_1, there exists a blue path between y_1 and y_2 whose interior points lie in P. Thus, by partitioning the vertices in Y_1 arbitrarily into pairs, we may cover all of them with at most ⌈| Y_1|/2 ⌉ blue paths. Adding a single-vertex path for each y∈ Y_0 and P to this collection, we obtain a blue path cover of K_n of size at most 1+⌈| Y_1|/2⌉+| Y_0|.
    Since any monochromatic path cover of [n] must have size at least f(n,χ), this yields

    f(n,χ) ≤ 1+⌈| Y_1|/2⌉+ | Y_0| <  2 + |Y_1|/2 + |Y_0| =2 + |Y|-|Y_0|/2 + |Y_0| = 2+ | Y|/2 + | Y_0|/2.



We now prove a weak version of <Ref>, which will bootstrap to prove <Ref> in full.


For all n∈ and C=160000, f(n)<√(n)+C.


 
We prove the claim by induction on n, noting that it is trivial for n≤ C. Suppose therefore that n>C and that f(m)<√(m)+C for all m<n and consider a colouring χ∈_n. Applying <Ref> with C=C_1=C_2, we obtain without loss of generality a blue path P such that the size of Y=[n]∖ V(P) is at most √(n)+8√(n)<3√(n)/2 and such that every y∈ Y has at least | X| - 2√(n) blue neighbours in X=V(P). By <Ref>, if | Y_0|≤√(n)/2 or | Y|≤√(n), then f(n,χ)≤√(n)+2 and there is nothing left to show. Let us therefore assume that | Y_0| >√(n)/2 and | Y| > √(n). 

On the other hand, we have that | X |≥ n-3√(n)/2≥ 3√(n)/2+2m for m=2√(n). Therefore, by applying <Ref>, we see that there must exist a collection of at most √(n) red paths that cover all vertices in Y and all but at most 6√(n) vertices in X. Let X'⊂ X denote the vertices that are not covered by these paths and recall that all edges between Y_0 and X, in particular those between Y_0 and X', are red. Since | Y_0|>√(n)/2 and | X'| <6√(n) we can cover all of X' with at most 12 red paths between X' and Y_0, which completes the proof.


We are now ready to prove <Ref>.


    Let C=160000, n_0 = C^10 and n>n_0. Define α_n = 9C/√(n), and suppose χ∈_n is such that f(n,χ)>√(n). By <Ref>, we have f(m)<√(m) +C for every m ∈. Applying <Ref> with C_1=C and C_2=0, we see that without loss of generality, there exists a blue path P such that the size of Y=[n]∖ V(P) is at most (1+α_n)√(n) and with the additional property that every vertex in Y has less than 2C√(n) blue neighbours in X =V(P). By <Ref>, if | Y_0|≤ (1-2α_n)√(n) or | Y|≤√(n)-1, then f(n,χ)≤√(n), a contradiction. Let us therefore assume that | Y_0| >(1-2α_n)√(n) and | Y| > √(n)-1. 

    We define H as the bipartite graph H on vertex set X∪ Y whose edges are the red edges between X and Y under χ. Let Y_1 = Y ∖ Y_0, X_0 = {x∈ X: d_H(x)=|Y|}, and X_1 = X∖ X_0. We have |Y_1|=|Y|-|Y_0| <(1+α_n)√(n)-(1-2α_n)√(n)  = 27Cn^1/4. By choice of P, we know that |{x∈ X: χ(xy) = blue}| < 2C√(n) for every y∈ Y, which implies that | X_1 | < 2C√(n)|Y_1|< 54C^2n^3/4. 
    Now, either Y_1 = ∅ = X_1, or, since n is sufficiently large, we have
    
    |X_0|/|Y_1|= |X|-|X_1|/|Y_1|>n-(1+α_n)n^1/2-54C^2n^3/4/27C n^1/4>n^1/2>108C^2n^3/4/(1-2α_n) n^1/2>2|X_1|/|Y_0|.

     
      
  
Either way, we may apply <Ref> to obtain a collection of at most ⌈ |X|/(|Y|+1) ⌉ paths in H covering all vertices in H. This corresponds to a red path cover in K_n, which implies that f(n,χ)≤⌈ |X|/(|Y|+1) ⌉. Since |Y|>√(n) -1, it follows that

 
   


    f(n,χ)≤⌈|X|/|Y|+1⌉ = ⌈n+1/|Y|+1⌉ -1
        ≤⌈√(n+1)⌉ -1
       
       ≤√(n).

Thus we have a contradiction, proving the theorem.




§ ACKNOWLEDGEMENTS

The second author is supported by the London Mathematical Society and the Heilbronn Institute for Mathematical Research through an Early Career Fellowship. The third author is supported by the Martingale Foundation.
plain



