title: Synchronizing Times for $k$-sets in Automata
authors: Natalie C. Behague J. Robert Johnson
text: 
  
  
  
  
  
  
  
  
  
  
  plain
  
  theoremTheorem
  prop[theorem]Proposition
  lemma[theorem]Lemma
  corollary[theorem]Corollary
  
  conjectureConjecture
  question[conjecture]Question
  
  
  
  remark
  remarkRemark
  subclaimClaim[theorem]
  
  definition
  definitionDefinition
  
   
  
  
  conjprime[1]
  
  	conjecture-1
  	
  	
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Synchronizing Times for k-sets in Automata
      Natalie C. Behague[Department of Mathematics and Statistics, University of Victoria, Victoria, BC, Canada    ],   Robert Johnson[School of Mathematical Sciences, Queen Mary University of London, London, UK ]
      December 30, 2023
  ===================================================================================================================================================================================================================
  
  
  
  
  
  
  An automaton is synchronizing if there is a word whose action maps all states onto the same state.  conjecture on the length of the shortest such words is one of the most famous open problems in automata theory. We consider the closely related question of determining the minimum length of a word that maps some k states onto a single state. 
  
  For synchronizing automata, we find a simple argument for general k almost halving the upper bound on the minimum length of a word sending k states to a single state. We further improve the upper bound on the minimum length of a word sending 4 states to a singleton from 0.5n^2 to ≈ 0.459n^2, and the minimum length sending 5 states to a singleton from n^2 to ≈ 0.798n^2. In contrast to previous work on triples, our methods are combinatorial. Indeed, we exhibit a fundamental obstacle which suggests that the previously used linear algebraic approach cannot extend to sets of more than 3 states.
  
  In the case of non-synchronizing automata, we give an example to show that the minimum length of a word that sends some k states to a single state can be as large as Θ(n^k-1). 
  
  
  
  
  § INTRODUCTION
  
  
  A (deterministic, finite) automaton  Ω consists of a finite set of states (usually labelled [n] = {1,2,…,n}) and a finite set of mappings, which are functions from the set of states to itself.  
  
  We shall be interested in the results of applying a sequence of mappings to the set of states. We call such a sequence of mappings a word of the automaton. The words of the automaton form a monoid, generated by the mappings, which acts on the set of states.
  
  We say that a word w of the automaton is a reset word if it sends every state to the same state; that is if w(i) = w(j) for all i,j. We call an automaton synchronizing if it has a reset word. The most famous and long-standing open problem on synchronizing automata is conjecture.
  
  
  Suppose an automaton on n states is synchronizing. Then the automaton has a reset word of length at most (n-1)^2.
  
  
  
  This conjecture comes from a particular family of automata, which we shall refer to as the automata. For each n ≥ 2, we define an automaton with states {1,2,…, n} and  two mappings f and g, defined as follows:
  
      f(i) = i+1 n        
      	g(i) = 
      	   
      	   2    if  i = 1 
      
      	   i    otherwise
  
  Figure <ref> shows the automaton for n=4, which has shortest reset word gfffgfffg.
  It is not too hard to check that the shortest reset word for the automaton on n states has length (n-1)^2. Thus if conjecture was true the bound would be best possible. 
  
  
  
  conjecture has been shown to hold for certain classes of automata, 
  including orientable automata <cit.>, automata where one mapping is a cyclic permutation of the states <cit.>,  and automata where the underlying digraph is Eulerian <cit.>. For a survey of these and other results see <cit.> or chapter 15 of the recent Handbook of Automata Theory <cit.>. It remains open to prove the conjecture for all automata. 
  
  One can easily obtain a naive upper bound on the length of a shortest reset word by observing that
   for any pair of states there is some word sending them to a single state, and the shortest such word will never pass through the same pair of states twice. Thus the shortest word sending a given pair of states to a single state is of length at most n2. Applying this repeatedly gives a reset word of length at most (n-1)n2.
  
  
  An improved upper bound for the length of a minimal reset word comes from a result due to Frankl and Pin <cit.> <cit.>. Rather than only considering the shortest word sending a given pair to a singleton, this instead bounds the length of the shortest word sending a given k-set to a (k-1)-set.
  
  Consider a synchronizing automaton with state set Ω of size n.
  Let S⊆Ω be a set of size k where k ≥ 2. There exists a word w of length at most n- k + 22 such that |w(S)| < k.
  
  
  Applying Theorem <ref> repeatedly, we get 
  
  An n-state synchronizing automaton has a reset word of length  ≤∑_i=2^n n- i + 22 = n^3 - n/6.
  
  
  This was the best known upper bound until relatively recently. Slight improvements to the constant factor have now been found:  Szykuła <cit.> obtained an upper bound of  ≈114/685n^3 + O(n^2) and Shitov  <cit.> refined this method to obtain an upper bound of ≈ 0.1654 n^3 + o(n^3).
  
  
  
  Let Ω be an automaton on [n]. The power automaton 𝒫(Ω), has as states the non-empty subsets of [n], and for each mapping f of Ω a corresponding mapping in 𝒫(Ω) taking S to f(S) for each set of states S.
  Figure <ref> shows the power automaton for the automaton in figure <ref>. We will think of the power automaton as a directed graph with labelled edges, and we say that the subsets of size k form the kth layer of the power automaton, written L_k.
  
  
  
  Now conjecture can be restated in terms of the power automaton:
  conj:cerny[conjecture]
  
  Let Ω be an automaton on [n]. 
  If the power automaton 𝒫(Ω) contains a path from [n] to a state in L_1,  then there exists such a path of length at most (n-1)^2. 
  
  
  This formulation of conjecture suggests the more general question of determining the length of the shortest path taking a k-set to a singleton. This was introduced by Gonze and Jungers <cit.> as the k-set rendezvous time and will be our focus in the first half of this paper.
  
  
  
  What is the minimum m such for any synchronizing automaton Ω on [n] there is a path in the power automaton 𝒫(Ω)  from L_k to L_1 of length at most m? Denote this minimum by (k,n).
  
  
  
  What is the minimum m such for any synchronizing automaton Ω on [n] and for any k-set S there is a path in the power automaton 𝒫(Ω)  from S to L_1 of length at most m? Denote this minimum by (k,n).
  
  
  Given an automaton Ω and a set of states S, we call S synchronizable if there exists a path from S to a singleton in the power automaton 𝒫(Ω). Let the weight t(S) of a set S be the shortest path from S to a singleton if S is synchronizable and ∞ otherwise.
  We define
  
      m(k,Ω)    = min{ t(S) : S ∈ L_k}
      
      M(k,Ω)    =max{ t(S) : S ∈ L_k, S  synchronizable}.
  
  Then (k,n) is the maximum of m(k,Ω) taken over all synchronizing automata and (k,n) is the maximum of M(k, Ω) again taken over all synchronizing automata. It is clear that (k,n) ≤(k,n) and (k,n) ≤ 1 + (k-1,n).
  
  Answering either of these questions in the case k=n is equivalent to answering conjecture.  
  Note that finding a lower bound on (k,n) or (k,n) requires a construction of a suitable automaton with all k-sets having large weight or one k-set having large weight respectively; while finding an upper bound on (k,n) or (k,n) requires an argument about all synchronizing automata.
  
  It is easy to see that (2,n) = 1. We have (2,n) ≤n2 since at worst some pair must travel through every other pair before reaching to a singleton. In fact, (2,n) = n2, where the example of a pair of weight n2 is the pair (2, ⌊n/2⌋ + 2) in the automaton on [n]. 
  
  
  The automaton also gives lower bounds for general k.
  We have that the minimum weight k-set is {1,2,…,k} with weight (k-2)n + 1 and so   (k,n) ≥ (k-2)n + 1.
  Gonze and Jungers <cit.> give a construction showing that (3,n) ≥ n+3 for odd n ≥ 9, which means in particular that the automaton is not extremal for the triple rendezvous time for such n. 
   
  Using the fact that (after the first time) it takes n moves to get two states one step closer to each other on the cycle, a k-set with states equally spaced around the circle has weight ≥⌊(k-1)n/k - 1⌋ n and so (k,n) ≥k-1/kn^2 - 2n. 
  More precisely, Cardoso <cit.> showed that the automaton on n states contains a k-set with weight at least  (n - 1)^2 - n-k/k(2n - k n/k-1 ), and thus 
  
      (k,n) ≥ (n - 1)^2 - n-k/k(2n - k n/k-1 ).
   Cardoso conjectured that this is the true value of (k,n).
  
  
  For upper bounds on (k,n) we can apply Theorem <ref>, which gives (k,n) ≤ 1 + ∑_i=2^k-1n-i+22 = k-2/2 n^2 + O(n) and 
  (k,n) ≤∑_i=2^k n-i+22 = k-1/2n^2+ O(n).
  
  In Section <ref> we give a simple argument that (k,n) ≤k-1/2n^2/2, thus almost halving the upper bound given by Frankl-Pin (indeed, for even k the coefficient of n^2 is exactly halved).
  
  We are also interested in upper bounds for specific values of k. Gonze and Jungers <cit.> proved that the triple rendezvous time (3,n) is bounded above by ≈ 0.1545 n^2 +O(n), using an approach based on linear programming. 
  Our main results on these questions are improved upper bounds for the 4-set and 5-set rendezvous times (4,n) and (5,n). In particular, we prove that (4,n) ⪅ 0.4589n^2 + O(n) and (5,n) ⪅ 0.7975n^2 + O(n). To do so, we first prove an upper bound on (3,n) that is weaker than the bound proved in <cit.> but which uses an approach that is both purely combinatorial and, crucially, generalisable to larger k. The proofs of these results are given in Section <ref>.
  
  In subsection <ref> we include a brief discussion of the triple rendezvous bound given in <cit.>, including an explanation of a link between the linear program used and the more familiar vertex cover number, and why this suggests their approach may be difficult to generalise to k larger than 3. 
  
  
  
  Table <ref> summarises what is known about (k,n) and (k,n), with the new results highlighted in red.
  
  
  We can also ask similar questions over all automata, not just synchronizing automata, and this will be our focus in the second half of the paper.
  
  
  What is the minimum m such that for any automaton Ω on [n],
  if the power automaton 𝒫(Ω) contains a path from L_k to L_1,  then there exists such a path of length at most m? Denote this minimum by ^*(k,n).
  
  
  
  What is the minimum m such that for any  automaton Ω on [n] and for any k-set S, if there is a path from S to L_1, then there is such a path of length at most m? Denote this minimum by ^*(k,n).
  
  
  In particular, ^*(k,n) is the maximum of m(k,Ω) taken over all automata Ω with at least one synchronizable k-set, and ^*(k,n) is the maximum of M(k,Ω) over the same collection of automata.
  
  Again we have that answering either question in the case k=n is again equivalent to conjecture. Note that ^*(k,n) ≤^*(k,n) and ^*(k,n) ≤ 1 + ^*(k-1,n).
  
  A similar question on the maximum length of a word resetting some subset of states of a non-synchronizing automaton was studied by Vorel <cit.> among others. In particular, Vorel proved that there exist non-synchronizing automata on n states with subsets taking 2^Ω(n) steps to synchronize.  We ask the slightly more specific question of what happens for sets of k states.
  
  
  
  A naive upper bound on ^*(k,n) is 1 + ∑_i=2^k-1ni,  since a shortest word down to a singleton will take a set through each set of size < k at most once. 
  
  A very slightly improved upper bound can be obtained by noting that an automaton is synchronizing if and only if for every pair of states u,v there is a word w with w(u) = w(v).  If the automaton is synchronizing then we can use the Frankl–Pin bound. If not, then there is a pair u,v that cannot be sent to the same state and any set containing both u and v is not synchronizable. The shortest path will not pass through any of these sets and so ^*(k,n) ≤  1 + ∑_i=2^k-1(ni - n-2i-2).
  In either case, for fixed k we have ^*(k,n) = O(n^k-1) and by the same argument ^*(k,n) = O(n^k).
  
  In Section <ref> we show that this is best possible — that is, if k is fixed then the answer to Question <ref> is Θ(n^k-1). Since ^*(k,n) ≥^*(k+1,n) - 1, we also get that ^*(k,n) = O(n^k). The non-synchronizing case therefore exhibits very different behaviour to the synchronizing case, which implies that any approach to conjecture using rendezvous times must use the condition that the automata is synchronizing in a critical way.
  
  
  
  Table <ref> summarises what is known about ^*(k,n) and ^*(k,n). The new contributions are highlighted in red.
  
  For the avoidance of confusion please note that throughout this paper we use the convention that when applying a word f_nf_n-1… f_2f_1 to a state v, we first apply the mapping f_1, then the mapping f_2 and so on, as with composition of functions. 
  
  
  
  
  § UPPER BOUNDS ON THE RENDEZVOUS TIME
  
  
  Frankl–Pin gives trivially that for 2 ≤ k ≤ n, the k-set rendezvous time (k,n) is at most 1 +  ∑_i=2^k-1n- i+22. The following simple adaptation of Frankl–Pin's result improves on this bound for k≥ 4.
  
   
  For all n and all 2≤ k≤ n the k-set rendezvous time (k,n) is  at most
  
      ∑_i=1^⌊k/2⌋i+12 + ∑_i=1^⌈k/2⌉ - 1n-i+12.
  
  In particular, for fixed k and n sufficiently large given k we have that 
      (k,n) < ⌊k-1/2⌋n^2/2 .
  
  
  
  By Frankl–Pin, there exists a word w that takes [n] to a set S of size n-⌊k/2⌋ of length at most 
      ∑_i=n - ⌊k/2⌋ + 1^nn- i+22 = ∑_i=1^⌊k/2⌋i+12.
  
  
  
  By the pigeonhole principle, there are at least n - 2⌊k/2⌋ states in S with exactly one state in their pre-image under w. 
  Take T to be n - k such states and let R = S∖ T. We have |R| = ⌈k/2⌉ and |w^-1(R)| = n - |w^-1(T)| = n - |T| = k.
  
  By Frankl–Pin again, we can find a word w' that takes R to a singleton of length at most
  
      ∑_i=2^⌈k/2⌉n-i+22 =  ∑_i=1^⌈k/2⌉ - 1n-i+12.
  
  Concatenating w'w gives the required word.
  
  
  We can also obtain improved bounds on the rendezvous time for k=4 and 5. We shall first consider the case k=3. The triple rendezvous time (3,n) was studied in particular by Gonze and Jungers <cit.>, who proved that (3,n) ≤√(5)-1/8n^2 + O(n) ≈ 0.1545n^2 + O(n). Theorem <ref> gives a weaker upper bound 
  (note that 3-√(5)/4≊ 0.1910) but it serves to illustrate the combinatorial approach that we will apply to the more complicated cases of k=4 and k=5.
  
  
   
  	For all n≥3, we have (3,n) ≤3-√(5)/4n^2 + 3/2n.
  
  
  For the sake of clarity, we will first prove the bound for strongly connected automaton, from which Theorem <ref> will follow as a corollary. An automaton is strongly connected if for any ordered pair of states u, v there is a word w such that w(u) = v. 
  
  We will need two further definitions. The image w of a word w is the set of states that are in the image of w thought of as a function. In particular, w = w([n]). The rank of a word is the number of states in its image.
  
   
  	Let Ω be a strongly connected synchronizing automaton on n ≥ 3 states. There exists some set S of three states and some word w of length ≤3-√(5)/4n^2 + 3/2n such that w(S) is a single state.
  
  
  
  	First, note that if n=3 then the triple rendezvous time is at most 4 and the result is trivially true.
  	Thus we may assume that n ≥ 4. 
  	
  	Let r be the minimum rank over all words of length at most n. Note that by Frankl–Pin there is a word of length 4 = 22 + 32 that takes [n] to a set of size n-2. Since n ≥ 4 we thus have that r ≤ n-2.
  	
  	Let w be a word of length ≤ n of minimal rank r. If r< n/2 then by the pigeonhole principle there must be some triple sent to a singleton by w and so we are done. We may therefore assume that r ≥n/2≥ 2.
  	
  	
  	 
  		There exists a word of length ≤ n + r+22 that takes some  triple to a singleton.
  	
  	
  		Let w be a word of length ≤ n of minimal rank r. If there is some triple which w sends to a singleton then we are done, so we can assume that w sends at most two states to the same state.
  		
  		Let S = {x: ∃ y  z  with  w(y) = w(z) = x}  be the set of states with pre-images of size 2 under w. Let T = w- S be the set of all states with a singleton pre-image under w.
  		We have that |S| + |T| = r and 2|S| + |T|= |w^-1([n])| = n, from which we obtain |S| = n-r.
  		
  		By Frankl–Pin there exists a word w' of length ≤n-(n-r)+22 = r+22 such that |w'(S)|<|S|.
  		In particular, there exist x  y in S with w'(x) = w'(y) = z. Take states u,v with w(u)=w(v) = x and s,t with w(s) =w(t)=y. 
  		The word w' w has length at most n + r+22 and w'w({u,v,s,t}) = w'{x,y}) = {z} so in this case w'w sends some 4-set to a single state.
  	
  	
  	  There exists a word of length ≤ n + (n-r)n/2 that takes some triple to a singleton.
  	
  	
  		We call an pair of states (u,v) good if there exists a word w_uv of length ≤ n with |w_uv^-1({u,v})| ≥ 3. We will count the number of good pairs.
  		
  		We can find a state z and a mapping f  with |f^-1(z)| ≥ 2. Since Ω is strongly connected, for each state v there is some word w_v of length ≤ n-1 with w_v(z) = v. In particular, (w_vf)^-1(v) ⊇ f^-1(z) where w_vf is a word of length ≤ m. For all a ∈ ((w_vf)∖{v} ) the pair (v,a) is good.
  		
  		Since w_vf is a word of length ≤ n, the rank of w_vf is ≥ r and so |((w_vf)∖{v})| ≥ r - 1 > 0.  Every state is in at least r - 1 good pairs and so the number of good pairs is at least (r-1) n/2 > 0. 
  		
  		The number of pairs in E that are not good is at most n2 - (r-1) n/2 = (n-r)n/2. We conclude that there is some word w  of length at most (n-r)n/2  that sends some good pair (u,v) to a singleton x, where the worst case scenario is having to pass through every not good pair first.
  		
  		By definition of good, we can find a word w_uv of length ≤ n with |w_uv^-1({u,v})| ≥ 3. 
  		Then w w_uv is a word of length at most n + (n-r)n/2 where (w w_uv)^-1 (x) ⊇ w_uv^-1({u,v}) has size at least 3. In particular, the claim holds.
  	
  	
  	
  	Combining the results of these two claims, we have that the triple rendezvous time for strongly connected automata is at most min{ n + r+22, n + (n-r)n/2}. The former is increasing in r while the latter is decreasing in r and so to find the maximum we look for the r where they are equal. This is when (r+2)(r+1) = (n-r)n, which occurs when r = -n-3 + √(5n^2 + 6n +1)/2  (subject to r≥ 0). 
  	
  	Substituting this in gives that the triple rendezvous time for strongly connected automata is at most 
  	
      n + (3n+3 - √(5n^2 + 6n + 1)) n/4   ≤ n + (3n+3 - √(5)(n + 1/√(5)) ) n/4
         = n + ((3-√(5))n + 2 ) n/4
         = 3-√(5)/4n^2 + 3/2n.
  
  	
  
  
  We can use the strongly connected case to prove Theorem <ref>.
  
  
  Let C be the sink component of the automaton, that is, the minimal non-empty set of states such that f(C)⊆ C for every f. 
  In particular, if w is any synchronizing word and x is the state with w([n]) = x then 
  C = {y : ∃ w'  with  w'(x) = y}. 
  Let m = |C| and let Ω' be the automaton restricted to C (with state set C and mappings that are the mappings of Ω restricted to C).
  
  
  Note that Ω' is strongly connected, and so if m ≥ 3 we can apply Theorem <ref> to Ω'. We obtain a word sending a triple to a singleton of length ≤3-√(5)/4m^2 + 3/2m ≤3-√(5)/4n^2 + 3/2n.
  
  Suppose that m ≤ 2. If m=2, write C = {x,y}. Since the automaton is synchronising, there must be some mapping g with g(x) = g(y). In addition, in Ω there must be some state z  x,y and some mapping f such that f(z) ∈ C. Note that f(C) ⊆ C, and so the word gf of length 2 takes the triple {x,y,z} to a singleton.
  
  Finally, suppose m=1 and let C = {x}. In Ω, there must be some state y  x and some mapping f such that f(y)=x. Let r be the rank of f.
  If r < n/2, then by the pigeonhole principle there must be some triple sent to a singleton by f and we are done. Suppose r ≥n/2. 
  For every state of Ω there is some word taking that state to x. Thus we can find  some state z in f∖{x} and some word w of length at most n-r+1 with w(z) = x, where the worst case scenario is having to pass through every state in [n] ∖f before reaching x. 
  Now wf is a word of length at most n-r + 2 ≤n/2 + 2 that takes the triple {x,y,z} to the singleton x.
  
  
  In a similar way we can improve the upper bounds on the 4-set and 5-set rendezvous times.
  
   
  For all n ≥ 4, we have 
  
      (4,n) ≤(3,n) +   (2 - √(3))n^2 + 2n - 1 ≤(11-√(5) - 4√(3)/4) n^2 + 7/2n -1.
  
  
  Note that 11-√(5) - 4√(3)/4≊  0.4589, so this is again an improvement on the 4+n2 given by Theorem <ref>.
  
   
  For all n ≥ 5, we have 
  
      (5,n) ≤(4,n) +  4 - √(7)/4n^2 + 3/2n -1 
      ≤(15-√(5) - 4√(3)-√(7)/4) n^2 + 5n -2.
  
  
  Note that 15-√(5) - 4√(3)-√(7)/4≊  0.7975, so this is again an improvement on the bound of 4+n2 + n-12 given by Theorem <ref>.
  
  To prove both Theorems <ref> and <ref> we will need two lemmas. In the case k=2 the lemmas correspond precisely to claims <ref> and <ref> in the proof of Theorem <ref> and we prove each lemma in an analogous way.
   
  Fix 2 ≤ k ≤ n-1 and l ≥ 1. Let Ω be a synchronizing automaton on n states and let r be the minimal rank over all words of length ≤ l in Ω. 
  Suppose that r ≤n-2 ⌈k/2⌉/⌊k/2⌋ 
   and let s = n -  ⌊k/2⌋ r/⌈k/2⌉≥ 2.
  Then 
      (k+1,n) ≤ l + n - s + 22.
  
  
  
  Let w be a word of length ≤ l of minimal rank r. If there is some (k+1)-set which w sends to a singleton then we are done, so we can assume that w sends at most k states to the same state.
  
  Let S = {x: |w^-1(x)| ≥⌈k+1/2⌉}  be the set of states with at least ⌈k+1/2⌉ pre-images under w. Let T = w- S   be the set of states with ≤⌊k/2⌋ pre-images under w.
  We have that |S| + |T| = r. We also have that n = |w^-1([n])| = |w^-1(S)| + |w^-1(T)| ≤ k|S| + ⌊k/2⌋|T|. Putting these together, we have k|S| +  ⌊k/2⌋ (r-|S|) ≤ n and so |S| ≥n -  ⌊k/2⌋ r/⌈k/2⌉≥ 2.
  
  By Frankl–Pin there exists a word w' of length ≤n-|S|+22 such that |w'(S)|<|S|.
  In particular, there exist x  y in S with w'(x) = w'(y) = z.
  We have that |(w'w)^-1(z)| = |w^-1(x,y)| ≥ 2⌈k+1/2⌉, so w'w sends some (k+1)-set to a single state.
  
  The length of the word w'w is 
  l + n-|S| + 22≤ l +  n- s + 22 where s =  n -  ⌊k/2⌋ r/⌈k/2⌉.
  
  
  
  	Fix 3 ≤ k ≤ n-1 and l ≥ 1. Let Ω be a synchronizing automaton on n states and let r be the minimal rank over all words of length ≤ l in Ω. 
  	Then there exists a word of length ≤(k,n) + n - 1 + (n-r)n/2 that sends some (k+1)-set to a singleton.
  
  
  We will first prove this Lemma for strongly connected automata.
   
  	Fix k ≤ n-1. Let Ω be a strongly connected synchronizing automaton on n states and let r be the minimal rank over all words of length ≤(k,n) + n - 1. Then there exists a word of length ≤(k,n) + n - 1 + (n-r)n/2 that sends some (k+1)-set to a singleton.
  
  
  
  	Let E = {(u,v) : u  v} be the set of pairs of states.
  	Let l = (k,n). We call an pair (u,v) ∈ E good if there exists a word w_uv of length ≤ l + n - 1 with |w_uv^-1({u,v})| ≥ k + 1. We will count the number of good pairs.
  	
  
  	There is a word w of length l = (k,n) that sends some k-set to a singleton x.
  	
  	Since Ω is strongly connected, for each state v there is some word w_v of length ≤ n-1 with w_v(x) = v. In particular, (w_vw)^-1(v) ⊇ (w)^-1(x) where w_vw is a word of length ≤ l + n - 1. For all a ∈ ((w_vw)∖ v ) the pair (v,a) is good.
  	
  	Since w_vw is a word of length ≤ l + n - 1, the rank of w_vw is ≥ r and so |((w_vw)∖{v})| ≥ r - 1 > 0.  
  	Every state in C is in at least r - 1 good pairs and so the number of good pairs is at least ≥(r-1) n/2 > 0. 
  	
  	The number of pairs in E that are not good is at most n2 - (r-1)n/2 = (n-r)n/2. 
  	We conclude that there is some word w  of length at most (n-r)n/2  that sends some good pair (u,v) to a singleton x, where the worst case scenario is having to pass through every not good pair first.
  	
  	By definition of good, we can find a word w_uv of length ≤ n with |w_uv^-1({u,v})| ≥ k+1. 
  	Then w w_uv is a word of length at most l + n-1 + (n-r)n/2 where (w w_uv)^-1 (x) ⊇ w_uv^-1({u,v}) has size at least k+1. In particular, the claim holds.
  
  
  We can now prove the more general statement for non-synchronizing automata.
  
  Let l = (k,n).
  Let C be the sink component of the automaton and let m = |C|. 
  Let Ω' be the automaton restricted to C and let r' be the minimal rank of a word of length l + n-1 restricted to Ω'. 
  
  Note that Ω' is strongly connected, and so if m ≥ k we can apply Theorem <ref> to Ω'. Since |_Ω' f| = |_Ω f ∩ C| ≥ |_Ω f|- (n-m), we have r' ≥ r - (n-m) and in particular, m-r' ≤ n-r.
  We obtain a word sending a (k+1)-set to a singleton of length ≤ l + m-1 + (m-r')m/2≤ l + n-1 + (n-r)n/2 and we are done.
  
  
  Suppose then that m ≤ k-1. 
  We know that there is a word w in Ω of length ≤ l that sends a k-set to a singleton and which therefore has rank ≤ n-k + 1. This tells us that r ≤ n-k+1. In particular, we have m ≤ k-1 ≤ n-r.
  We will show that there is a word of length ≤ l + 2(n-m) + m2 that takes some (k+1)-set to a singleton.
  
  
  There is a word w of length l = (k,n) that sends some k-set to a singleton x.
  We can then find a word w_1 of length at most n-m that sends x to a state z ∈ C, where at worst we have to go through every state not in C before we reach C. 
  In particular, |(w_1w)^-1 (z) | ≥ k where w_1w is a word of length ≤ l + n - m.
  
  If z is the only state in ( w_1w) 
  then w_1w is a synchronizing word sending 
  n ≥ k+1 states down to a singleton. 
  So suppose (w_1w) - z is non-empty and take some v ∈(w_1w), v  z. 
  We can find a word w_2 of length ≤ n-m that takes v to a vertex y ∈ C.
  
  If w_2(z) = y then the word w_2 w_1 w of length ≤ l + 2(n-m) has |(w_2 w_1 w)^-1(y)| = |(w_1w)^-1(z,v)| ≥ k + 1. 
  Otherwise, y, w_2(z) are two distinct vertices in C and we can find a word w_3 of length at most m2 that takes {y, w_2(z)} to a singleton. 
  Then w_3w_2w_1w is a word of length ≤ l + 2(n-m) + m2 that takes some (k+1)-set to a  singleton.
  
  To prove that the bound as stated in the lemma holds, it suffices to show that the following quantity is positive. 
  
      (n - 1 + (n-r)n/2) - (2(n-m) + m2) 
      =  n(n-r-2) -m^2 + 5m - 2/2
  
  Note that since there is a word of length ≤ l that sends a k-set to a singleton, we have a word of length l of rank ≤ n-k + 1. This implies that r ≤ n-k+1, and so in particular n-r-2 ≥ 0.
  If m=1, we are already done. Otherwise, m ≥ 2 and substituting m ≤ n-r, we obtain
  
      n(n-r-2) -m(m-5) - 2/2   ≥ (m+r)(m-2) -m^2 + 5m - 2/2
         = (m-2)r+3m -2/2≥ 0.
  
  
  
  
  We use these lemmas to prove the Theorems.
  
  Fix n ≥ 4. Let l =  (3,n) + n-1 and let r be the minimal rank of a word of length at most l. 
  
  Applying the k=3 case of Lemmas <ref> and <ref> we get
  
      (4,n) ≤ 
      		l + 1/2(n+r/2+2)(n+r/2+1)    if  r≤ n-4
      
      		 l + 1/2(n-r)n    for all  r
  
  
  If r > n-4 then 1/2(n-r)n < 2n.
  
  If r ≤ n-4, the first bound is increasing with r (for r ≥ 0) and the second is decreasing with r so the maximum is obtained where the two are equal, that is when 
  (n+r/2+2)(n+r/2+1) = (n-r)n. Rearranging gives 
  r^2 + 6(n+1)r -(3n^2 - 6n - 8) = 0.
  Solving for r, we get that the maximum is obtained when 
  
      r = -3(n+1) + √(12n^2 + 12n + 1)
  
  
  Thus we have that the maximum is
  
      (n-r)n/2   = (4n + 3 - √(12n^2 + 12n + 1))n/2
         ≤(2n + 3/2 - √(3)(n + 1/√(12)))n 
          = (2 - √(3))n^2 + n
  
  
  
  Putting this together with the bound on (3,n) from Theorem <ref> we get the final bound 
  
      (4,n) ≤(3-√(5)/4 + 2-√(3)) n^2 + 7/2n - 1.
  
  
  
  
  
  Fix n ≥ 5. Let l =  (4,n) + n-1 and let r be the minimal rank of a word of length at most l. 
  
  Applying the k=4 case of  Lemmas <ref> and <ref> we get
  
      (5,n) ≤ 
      		l + 1/2(n+2r/2+2)(n+2r/2+1)    if  r≤n-4/2
      
      		 l + 1/2(n-r)n    for all  r
  
  
  If r > n-4/2 then 1/2(n-r)n < 1/4n^2 +n.
  
  If r ≤n-4/2, the first bound is increasing with r (for r ≥ 0) and the second is decreasing with r so the maximum is obtained where the two are equal, that is when 
  (n+2r/2+2)(n+2r/2+1) = (n-r)n. Rearranging gives 
  r^2 + (2n+3)r -(3/4n^2 - 3/2n - 2) = 0.
  Solving for r, we get that the maximum is obtained when 
  
      r = -(2n+3) + √(7n^2 + 6n + 1)/2
  
  
  Thus we have that the maximum is
  
      (n-r)n/2   = (4n + 3 - √(7n^2 + 6n + 1))n/4
         ≤(4n + 3 - √(7)(n + 1/√(7)))n/4
          = 4 - √(7)/4n^2 + 1/2n
  
  Putting this together with the bound on (4,n) from Theorem <ref> we get the final bound.
  
  
  
  It is clear that we could continue applying this method in the way we have here to obtain upper bounds on (k,n) for larger k. However, as it stands the method does not give an improvement on the bound ((k,n) < ⌊k-1/2⌋n^2/2 given by Theorem <ref> for larger k. We remain hopeful that the method could be improved upon to give results for larger k. One approach might be to alter Lemma <ref> to allow one to go directly from a result about (k,n)  to a result about (k+c,n) for c larger than 1.
  
  
  
  
   §.§ A Discussion of Gonze and Jungers' Result
   
  Gonze and Jungers prove in Theorem 3.13 of <cit.> that for strongly connected synchronizing automata the triple rendezvous time (3,n) is at most √(5)-1/8n^2 + O(n) ≤ 0.16 n^2 + O(n). To do so, they used a linear program first introduced in <cit.>. 
  
  We will discuss a correspondence between this linear program  and the more well-known fractional vertex cover number. 
  This connection to a better understood linear program is interesting in its own right and could potentially lead to improvements to the triple rendezvous time. Unfortunately, this correspondence also suggests that this linear programming approach cannot be straightforwardly generalised to give upper bounds on k-set rendezvous times for k>3. We explain why at the end of this section.
   
  First, let us state the original linear program defined in <cit.>. Fix an automaton Ω on n states.
  If t < (3,n), the sets for which there is a word of length ≤ t sending that set to a singleton will only be singletons and pairs. We let G_t be the graph on n states with edge-set all such pairs, and let m(t) = e(G_t) be the number of such pairs. 
  
  Let A(t) be a matrix with rows indexed by [n] and columns indexed by the sets of Ω that can be sent to a singleton by a word of length ≤ t. A column corresponding to the set S will have a 1 in rows indexed by elements of S and a 0 in all other rows. For example, A(0) will be the n × n identity matrix. In general, A(t) will have n+m(t) columns for t<(3,n).
  
  Define Prog_A(t) to be the linear program
  
      [b] min_p,k k 
      s.t.      pA(t) ≤ ke_n+m(t)
         e_np^𝖳 = 1 
         p≥0
  
  where p is a row vector of length n and e_i  is the all ones row vector of length i.
  Let k(t) be the minimum value attained by Prog_A(t) and let P_t be the set of optimal solutions p to Prog_A(t).  
  
  The linear program Prog_A(t) can be thought of in terms of assigning weights to G_t. The vector p assigns a weight to each vertex of G_t such that the sum of all the weights is one. The condition pA(t) ≤ ke_n+m(t) means that for each vertex and edge of G_t the sum of the weights on the incident vertices is at most k. Then k(t) is minimal subject to a weighting of G_t existing that satisfies these conditions. 
  
  A critical part of the proof in <cit.> is that the set of possible minimum values k(t) attained by Prog_A(t) is small. This is used together with an argument showing that as t increases, either k(t) decreases or the dimension of the solution space decreases and so there is a bound on how large t can grow.
  
  We can rewrite Prog_A(t) in the form of a more well-known linear program. We will do this in two stages. 
  First, define E(t) to be a matrix with rows indexed by [n] and columns indexed by the edges of G_t, where the column indexed by edge ij has a 1 in rows i and j and 0s elsewhere. Now A(t) is the concatenation of the n × n identity matrix I_n and E(t), and so the statement pA(t) ≤ ke_n+m(t) is equivalent to the statements p≤ ke_n and pE(t) ≤ ke_m(t). We rewrite Prog_A(t) as follows: 
  
  	
      min_p,k k 
      s.t.      pE(t) ≤ ke_m(t)
         e_np^𝖳 = 1 
         p≥0
         p≤ ke_n  1*
   
  
  
  We now rescale this linear program. Define r = e_n - 1/kp and s = n - 1/k. Substituting into <ref> and rearranging (noting that e_n E(t) = 2e_m(t) and so on) we obtain the equivalent linear program Prog_B(t) :
  
      [b] min_r,s s 
      s.t.      rE(t) ≥e_m(t)
         e_nr^𝖳 = s 
         r≤e_n 
         r≥0
  
  
  Let s(t) be the minimum value attained by Prog_B(t) and let R_t be the set of optimal solutions r to Prog_B(t).  
  If we restrict r to having only entries in {0,1} we get the standard integer linear program for the minimum vertex cover problem. A solution r assigns weights 0 or 1 to the vertices of G_t such that the total weight assigned is s. The condition rE(t) ≥e_m(t) means that for each edge of G_t the sum of the weights of the incident vertices is at least one — the edge is `covered' by the vertices. The value of s(t) is then the minimum total weight over all such vertex covers r.
  
  Thus Prog_B(t) is  the relaxation of the integer linear program for the minimum vertex cover problem. As a result Prog_A(t) is in direct correspondence with the more well-studied fractional vertex cover problem.
  
  
  It is well known (and straightforward to show) that s(t) must always be half integral and, what is more, there is always an optimal solution r with entries taken only from {0,1/2,1}.
  One immediate outcome of this correspondence is therefore that is an easy proof that the value of k(t) must be of the form 2/n + n_1 where n_1 is an integer between 0 and n. This fact formed a crucial part of the proof in <cit.>. 
  
  
  Suppose we wanted to generalise this linear programming approach to get upper bounds on  the k-set rendezvous time for k>3. One can construct an analogous linear program to Prog_A(t) and similarly transform it into an analogous linear program to Prog_B(t). The resulting Prog_B(t) is the fractional relaxation of a hypergraph minimum vertex cover problem where hyperedges of size i must be covered i-1 times. That is, a solution r assigns a weight to each vertex such that the sum of the weights of vertices in an i-edge is at least i-1. 
  
  The hypergraph version does not have the nice half integral property that the graph version has, even in the smallest case k=4. 
  The relevant fractional vertex cover problem is to find, for a hypergraph H with edges of size 2 and 3, the minimum total weight (H) of a fractional vertex cover  that covers each 2-edge with weight one and each 3-edge with two.
  The following Lemma proves that not only is this not half integral, but in fact there can be no integer p where the set of possible values are of the form i/p for i ∈ℕ.
  
   
  For all j ∈ℕ there exists a hypergraph H such that the minimum total weight (H)  of a fractional vertex cover that covers each 2-edge with weight one and each 3-edge with weight two is s/2^j for some odd integer s.
  
  
  Let H_j have 3j vertices labelled x_1,…,x_j, y_1,…, y_j and z_1,… z_j. Add the 2-edges {x_1, y_1}, {y_1, z_1} and {z_1,x_1} and all 3-edges of the form {x_i, y_i-1, z_i}, {y_i, z_i-1, x_i}, {z_i, x_i-1, y_i} for 2 ≤ i ≤ j. (You can also add 2-edges that are subsets of a 3-edge and it will not change the argument.)
  Fix a  fractional vertex cover of H_j with minimum total weight. For a vertex set S let w(S) denote the total weight of that set. 
  
  Let a_1,…, a_j be positive rationals satisfying the j simultaneous equations 2a_1 + a_2 = 2a_2 + a_3 = … = 2a_j-1 + a_j = 2a_j = 1. Note that summing these equations gives j = 2a_1 + 3∑_i=2^ja_j. We have:
  
  
      (H_j) = w(H_j) =     ∑_i=1^j 2a_i(w(x_i)+w(y_i) +w(z_i))  + ∑_i=2^j a_i(w(x_i-1)+w(y_i-1)+ w(z_i-1))
      
      =      a_1( w({x_1, y_1}) + w({y_1, z_1}) + w({z_1,x_1}) ) 
          + ∑_i=2^ja_i (w({x_i, y_i-1, z_i}) + w({y_i, z_i-1, x_i}) + w({z_i, x_i-1, y_i}) ) 
      ≥    3a_1 +  ∑_i=2^j6a_i 
      
      =      2j - a_1
  
  
  We will show by induction that for 1 ≤ l ≤ j, a_j+1- ℓ = s_ℓ/2^ℓ for some odd integer s_ℓ. For the base case note a_j = 1/2. For the inductive step, let 1 ≤ℓ < j and suppose the statement is true for a_j+1-ℓ. We have a_j-ℓ =  1 - a_j+1-ℓ/2 and so the inductive hypothesis holds. In particular, the value of 2j - a_1 is s/2^j for some odd integer s.
  
  The final step of the proof is to show that this lower bound is attainable. Let w(x_i) = w(y_i) = w(z_i) = 1 -  a_j+1-i. It is easy to check that the total weight on the 2-edges is one and the total weight on the 3-edges is two. Furthermore, the total weight over all vertices is 3j - 3a_1 - ∑_i=2^j a_i = 2j - a_1 as required.
  
  
  For every i,j ∈ℕ there exists a hypergraph H where (H) is i/2^j more than an integer.
  
  
  If H_1 + H_2 is the disjoint union of two hypergraphs H_1 and H_2, then (H_1+H_2) = (H_1) + (H_2). Thus by taking disjoint unions of the appropriate H_j given by Lemma <ref> we can obtain any residue of the form i/2^j where i,j ∈ℕ.
  
  
  The proof of the triple rendezvous time upper bound uses as a critical component that there are a small number of possible minimum values of the linear program Prog_A(t), which follows from the half integrality of Prog_B(t). We can see via the correspondence to the fractional vertex covers and Corollary <ref> that there is no similarly straightforward bound on the number of possible minimum values when we generalise to k>3, and so this approach cannot be trivially generalised.
  
  
  
  § NON-SYNCHRONIZING AUTOMATA WITH LARGE RENDEZVOUS TIME
  
  
  
  We now turn to the second half of the paper, which concerns rendezvous times in non-synchronizing automata.
  We will prove a lower bound on ^*(k,n) via a construction of a suitable automaton. To introduce the main idea of the construction we give the simpler k=3 case first.
  
  For every sufficiently large n, ^*(3,n) > n^2/8.
  
  
  For every n we will construct an automaton on [n] where the minimal weight of a k-set is greater than n^2/8. 
  
  Partition [n] into A and X, where |A| = ⌊n/4⌋.
  
  Label the states of A by a_1,a_2,…,a_|A| and label the states of X by x_1,x_2,…,x_|X|.
  
  Take two functions f and g as follows, as shown in figure <ref> where f is drawn in blue and g in red.
  
      f(x_t)    = x_(t+1 |X|)
      
      f(a_|A|)    = a_1 
      
      f(a_j)    = x_j  for  j  |A|
      
      
      g(x_t)    =   
      	 
         		x_t+1   if  1 ≤ t ≤ |A| - 1
      
         		x_t - |A| + 1   if  t = |A|
      
         		x_t    otherwise
      
      g(a_j)    = a_(j+1 |A|)
  
  
  
  
  Note that f and g restricted to X are permutations on X and so any set containing more than one state in X cannot be synchronized. 
  Moreover, any set containing three states in A cannot be synchronized: the image of such a set under g still has three states in A, and the image under f contains two states in X. 
  
  It follows that a synchronizable triple must contain two states in A and one state in X.
  Fix such a triple S and consider a word that synchronizes this set acting on it. We will obtain that the triple of minimal weight is in fact {x_|X|, a_1, a_|A|}.
  
  Note that for a shortest word from a triple to a singleton the first step must map a triple to a pair. In particular, the first map of the shortest word must be f, as g is a permutation.
  The triple S must contain two states in A, one of which must be a_|A| otherwise applying f gives two states in X. Let the other be a_t, where 1 ≤ t ≤ |A|-1. 
  After applying f, we have the states a_1 and x_t, which must be the only state in X. 
  
  Note that 
  
      fg^l-1(a_1) = 
       
      	a_1    if  l ≡ 0 |A|
      
      	x_(l |A|)   otherwise
  
  and for  1 ≤ t ≤ |A|-1,
  
      fg^l-1(x_t) =
       
      	x_|A| + 1   if  t + l - 1 ≡ 0 |A|
      
      	x_(t+l |A|)   otherwise.
      .
  
  
  This means that applying fg^l-1 gives two states in X for every l ≢0 |A|. Thus the next step must be to apply  fg^l-1 where l is some multiple of |A|. This sends a_1 and x_t to themselves unless t=1, in which case x_t is sent to x_|A|+1.
  
  
  To further reduce the size of the set, we must map x_|A|+1 and a_1 to the same state. To do this, we must move the state in position x_|A| + 1 round through x_|A| +2, x_|A| +3,… until we reach x_|X|, without moving the second state that is currently in A into X as we do so.
  
  Suppose we have just applied f, and we now want to move x_s to x_s+1 without adding any extra states into X (where s is some value not in {|X|, 1,2,3 …, |A|}). 
  Since we have just applied f, the state in A must be at position a_1 (having just come from position a_|A|).
  We need to apply f to move x_s, but we can only apply f when the state in A is at position a_|A| and so we must first apply g^|A|-1 to move the state at a_1 to be at a_|A|. Only then can we apply f, and so the shortest word moving x_s to x_s+1 is fg^|A|-1.
  
  Repeatedly applying this, we have that the shortest word squashing a triple to a singleton is f(fg^|A|-1)^(|X| - (|A|+1))fg^|A|-1f which has length 
  
      1 + (|X| - |A|)|A| +1 =  (n - 2⌊n/4⌋) ⌊n/4⌋ + 2 >  n^2/8.
  
  
  
  The general case extends the construction given in Theorem <ref>. We still have two mappings and a set of states X on which both mappings act as permutations, meaning that any synchronizable set has at most one state in X. Rather than having a single gadget A  we will need k-2 gadgets A_0,A_1,A_k-3, each with the same structure as A but of coprime sizes. 
  
  To synchronize a k-set we will need to apply a mapping f to move a state around X. As before, we will not be able to apply f without first applying the other mapping g several times to move the state in each A_i from a^(i)_1 to a^(i)_0. Because we chose the A_i to have coprime sizes, each such move will neccessitate many applications of g.
  
  
  Let k≥ 3. For every n sufficiently large, ^*(k,n) ≥4/3(n/4k)^k-1.
  
  
  
  Fix the integer k. 
  For every n we will construct an automaton on [n] where the minimal weight of a k-set is 4/3(n/4k)^k-1. 
  
  Partition [n] into A_0,A_1,A_2,…,A_k-3 and X, where n/4k≤ |A_i| ≤n/3k and 
  
  {A_0 ,A_1 , A_2 , …, A_k-3} = 1. This is possible for n sufficiently large, for example by the prime number theorem. 
  
  Label the states in each A_i by a^(i)_1,a^(i)_2,a^(i)_3,… and label the states of X by x_1,x_2,x_3….
  Let q = ⌊2n/3k⌋.
  
  Take two functions f and g as follows, as shown in figure <ref> where f is drawn in blue and g in red.
  
      f(x_t)    = x_(t+1 |X|)
      
      f(a^(i)_j)    = 
      	 
         		a^(i)_1    if  j=|A_i| 
      
         		x_iq + j   otherwise
      
      
      g(x_t)    =   
      	 
         		x_t+1   if  iq + 1 ≤ t ≤ iq + |A_i| - 1  for some  i
      
         		x_t - |A_i| + 1   if  t = iq + |A_i|   for some  i
      
         		x_t    otherwise
      
      g(a^(i)_j)    = a^(i)_(j+1 |A_i|)
  
  
  
  
  Note that f and g restricted to X are permutations on X and so any set containing more than one state in X cannot be synchronized. 
  
  Moreover, any set containing three states in some A_i cannot be synchronized: the image of such a set under g still has three states in A_i, and the image under f contains two states in X. 
  Similarly, any set containing two states in A_i and two states in A_j for some distinct i and j also cannot be synchronized.
  
  It follows that a synchronizable set of size k must contain two states in some A_i, one state in every other A_j and one state in X.
  Fix such a set S and consider a word that synchronizes this set acting on it. 
  
  For a shortest word from a triple to a singleton the first step must map a triple to a pair and so the first map must be f.
  The set S contains two states in A_i, one of which must be a^(i)_|A_i| else applying f gives two states in X. Let the other be a^(i)_t, where 1 ≤ t ≤ |A_i|-1. 
  After applying f, we have the states a^(i)_1 and x_iq+t, which must be the only state in X. 
  
  Note that 
  
      fg^l-1(a^(i)_1) = 
       
      	a^(i)_1    if  l ≡ 0 |A_i|
      
      	x_iq+(l |A_i|)   otherwise
  
  and 
  
      fg^l-1(x_iq+t) =
       
      	x_iq+|A_i| + 1   if  t + l - 1 ≡ 0 |A_i|
      
      	x_iq+(t+l |A_i|)   otherwise
      .
  
  Since 1 ≤ t ≤ |A_i|-1 this means that applying fg^l-1 gives two states in X for any l ≢0 |A_i|. Thus the next step must be to apply  fg^l-1 where l is some multiple of |A_i|. This sends a^(i)_1 and x_iq+t to themselves unless t=1, in which case x_iq+t is sent to x_iq+|A_i| + 1.
  
  To further reduce the size of the set, we must map the state in X and some state in some A_j to the same state. To do this, we must move the state x_iq+|A_i| + 1 in X round to be in { x_jq,  x_jq+1, …, x_jq+|A_j| - 2}, without adding extra states to X as we do so.
  
  Suppose we have just applied f, and we now want to move x_s to x_s+1 without adding any extra states into X (where s is some value not in { x_jq+1,  x_jq+2, …, x_jq+|A_j| - 1} for any j). 
  Since we have just applied f, the state in each A_j must be at position a^(j)_1 (having just come from position a^(j)_|A_j|).
  We must apply f to move x_s, but we can only apply f when for each A_j, the state in A_j is at position a^(j)_|A_j|. 
  Thus we must use g to move the state at a^(j)_1 to be at a^(j)_|A_j| for each j. 
  
  The number of times g is applied must be congruent to -1 modulo |A_j| for all j. 
  Since |A_0|, |A_1|, …, |A_k-3| are coprime, the smallest such number is ∏_j=0^k-3 |A_j| - 1. 
  This is followed by an application of f and so it takes at least ∏_j=0^k-3 |A_j| steps to move x_s to x_s+1.
  
  Applying this repeatedly, we see that the length of a word taking the state in X from x_iq+|A_i| + 1 to some state of the form { x_jq,  x_jq+1, …, x_jq+|A_j| - 2} without introducing a second state to X must be at least
  
      (q - (|A_i| - 1))∏_j=0^k-3  |A_j| 
      ≥(2n/3k - n/3k)(n/4k)^k-2 = 4/3(n/4k)^k-1.
  
   
  
  
  Theorem <ref>, together with the observation that a minimal length path from some k-set to a singleton passes through each set of size <k at most once, tells us that ^*(k,n) = Θ(n^k-1) for fixed k. Since ^*(k,n) ≥^*(k+1,n) - 1 we have as an immediate consequence that ^*(k,n) = Θ(n^k-1).
  
  
  These results are very different from the situation for synchronizing automata.
  One thing we learn therefore is that any bound on the k-set rendezvous time (k,n) must use the fact that the automata are synchronizing as a crucial part. In particular, this impacts any attempt at a proof or improved bound for conjecture that relies on bounding the k-set rendezvous time — such a proof must use somewhere that all pairs (and all sets) are synchronizable.
  
  
  
  § OPEN QUESTIONS
  
  
  As mentioned at the end of Section <ref>, it may be possible that the tools used to prove Theorems <ref>, <ref> and <ref> could be extended further and combined with new ideas to give improved upper bounds on  (k,n) for k>3. To do so, one would have to strengthen Lemma <ref> and/or Lemma <ref>.
  
  We believe something stronger may be true, at least for small k. We know from <cit.> that the triple rendezvous time (3,n) ⪅ 0.1545 n^2 +O(n). However, the best known lower bound to (3,n) is n+3. Given the lack of any examples to the contrary, we conjecture that the triple rendezvous time is in fact linear in n.
    There exists some constant c such that (3,n) ≤ c n for all n.
  
  Any techniques involved in the proof of Conjecture <ref> may well generalise to give improved bounds on the k-set rendezvous time (k,n) and potentially (n,n), the bound itself.
  
  We can also ask about improved bounds on (3,n), which is known to be between 2/3n^2 + O(n) and n^2 + O(n). 
   Is there some constant c < 1 such that (3,n) ≤ cn^2 + O(n)? 
  
  A positive answer to  this question would give an improvement to the Frankl–Pin bound for the length of a shortest reset word from  n^3/6 to  c'n^3 for come constant c'<1/6. The reason for this is that for k ≥ 3 we would have from any k-set there is a path to a  (k-2)-set of length ≤ cn^2. This is an improvement on the Frankl–Pin bound n-k+22 + n-k+32 for k < (1-√(c))n, that is, a linear proportion of all k.
  
  There is nothing special about triples here: an improved upper bound on (k,n) for any fixed k would give a improvement on the Frankl–Pin bound in a similar way. We also don't have to be restricted to paths from k-sets to singletons — one can ask the same questions about the shortest path from a k-set to an l-set for any k > l and draw similar conclusions from any improved bounds.
  
  Theorem <ref> shows that for fixed k we have ^*(k,n) = Θ(n^k-1). A natural question to ask is what are the correct asymptotics for ^*(k,n)? In the case k=3 we have n^2/8≤^*(k,n) ≤n^2 - n -1/2.
  
  Is there an automaton which attains ^*(3,n) = (1/2+o(1))n^2?
  
  An upper bound on the minimum weight of a triple ^*(3,n) is the total number of synchronizable pairs plus one. To get  a minimum weight triple of weight (1/2+o(1))n^2 we would need the automaton to be almost synchronizing in the sense that all but an arbitrarily small proportion of pairs are synchronizable.
  
  Consider the construction given in the proof of Theorem <ref>. We know that a pair of states both in X is not synchronizable. In fact, it is straightforward to check that only pairs of the following forms are synchronizable:
  
  
    * {a_i,x_s} for i ∈{1,2,3,…, |A|} and s ∉{1,2,3,…,|A|},
  
    * {a_i,x_i} for i ∈{1,2,3,…, |A|},
  
    * {a_1, x_|A|} and (a_i,x_i-1) for i ∈{2,3,…, |A|},  and 
  
    * {a_i,a_(i+1 |A|)} for i ∈{1,2,3,…, |A|}.
    
  In particular, the automaton has |A|(|X| - |A|) + 3|A| = n^2/8 + O(n) synchronizable pairs. We have that the number of synchronizable pairs and the minimum weight of a triple are asymptotically equal in this example. Is it possible to construct an automaton with this same property where a larger proportion of pairs are synchronizable?
  
  We also note that our construction is not strongly connected. Could there be a strongly connected automaton with the same properties, that is, with only two mappings and needing time Ω(n^k) to synchronize a k-set? 
  
  
  Dub98
  
  [Car14]Car14
  Ângela Filipa Pereira Cardoso.
  The Cernỳ Conjecture and Other Synchronization Problems.
  PhD thesis, Universidade do Porto (Portugal), 2014.
  
  [Čer64]Cer
  J Černỳ.
  Poznámka k homogénnym eksperimentom s konečnỳmi
    automatami. matematickofyzikálny časopis slovenskej akadémie
    vied, 14 (3): 208–216, 1964.
  Slovak zbMATH, 1964.
  
  [Dub98]Dub98
  Louis Dubuc.
  Sur les automates circulaires et la conjecture de černỳ.
  RAIRO-Theoretical Informatics and Applications, 32(1-3):21–34,
    1998.
  
  [Epp90]Epp90
  David Eppstein.
  Reset sequences for monotonic automata.
  SIAM Journal on Computing, 19(3):500–510, 1990.
  
  [Fra82]Fra82
  Peter Frankl.
  An extremal problem for two families of sets.
  European Journal of Combinatorics, 3(2):125–127, 1982.
  
  [GJ16]GJ16
  François Gonze and Raphaël M. Jungers.
  On the synchronizing probability function and the triple rendezvous
    time for synchronizing automata.
  SIAM J. Discrete Math., 30(2):995–1014, 2016.
  
  [Jun12]Jun12
  Raphaël M Jungers.
  The synchronizing probability function of an automaton.
  SIAM Journal on Discrete Mathematics, 26(1):177–192, 2012.
  
  [Kar03]Kar03
  Jarkko Kari.
  Synchronizing finite automata on eulerian digraphs.
  Theoretical Computer Science, 295(1-3):223–232, 2003.
  
  [KV21]KV21
  Jarkko Kari and Mikhail Volkov.
  Cerny’s conjecture and the Road Coloring Problem.
  Chapter 15 in 
  J Pin (ed.), Handbook of Automata Theory, Volume I, 
  EMS, 2021.
  
  [Pin83]Pin83
  Jean-Éric Pin.
  On two combinatorial problems arising from automata theory.
  In North-Holland Mathematics Studies, volume 75, pages
    535–548. Elsevier, 1983.
    
  [Shi19]Shi19
  Yaroslav Shitov.
  An improvement to a recent upper bound for synchronizing words of
    finite automata.
  J. Autom. Lang. Comb., 24:367–373, 2019.
  
  [Szy18]Szy18
  Marek Szykuła.
  Improving the upper bound and the length of the shortest reset words.
  In 35th Symposium on Theoretical Aspects of Computer
    Science, volume 96 of LIPIcs. Leibniz Int. Proc. Inform., pages Art.
    No. 56, 13. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018.
  
  [Vol08]Vol08
  Mikhail V. Volkov.
  Synchronizing automata and the Černý conjecture.
  In Language and automata theory and applications, volume 5196
    of Lecture Notes in Comput. Sci., pages 11–27. Springer, Berlin, 2008.
  
  [Vor16]Vor16
  Vojtěch Vorel.
  Subset synchronization and careful synchronization of binary finite
    automata.
  International Journal of Foundations of Computer Science,
    27(05):557–577, 2016.
  
  
  
  
  
  