Maximum Size of a Family of Pairwise Graph-Different Permutations
Louis Golowich Chiheon Kim Richard Zhou

[NO \title GIVEN]
    [NO \author GIVEN]
    December 30, 2023
======================


Two permutations of the vertices of a graph G are called G-different if there exists an index i such that i-th entry of the two permutations form an edge in G. We bound or determine the maximum size of a family of pairwise G-different permutations for various graphs G. 

We show that for all balanced bipartite graphs G of order n with minimum degree n/2 - o(n), the maximum number of pairwise G-different permutations of the vertices of G is 2^(1-o(1))n. We also present examples of bipartite graphs G with maximum degree O(log n) that have this property. We explore the problem of bounding the maximum size of a family of pairwise graph-different permutations when an unlimited number of disjoint vertices is added to a given graph. We determine this exact value for the graph of 2 disjoint edges, and present some asymptotic bounds relating to this value for graphs consisting of the union of n/2 disjoint edges.





§ INTRODUCTION

For any graph G, let two permutations of the vertices of G be G-different if there exists some index i such that the i-th entry of the two permutations form an edge in G. Let F(G) be the maximum size of a family of pairwise G-different permutations of the vertices of G.

The value of F(G) has been studied for many graphs G. One of the most studied such graphs is the path on n vertices P_n (pairs of P_n-different permutations are also called colliding permutations in <cit.>). Körner and Malvenuto <cit.> conjectured that F(P_n) = n ⌊ n/2 ⌋. The authors' results implied that 

    F(G) ≤n ⌊ n/2 ⌋

for all n-vertex balanced bipartite graphs G, and F(K_⌊ n/2 ⌋, ⌈ n/2 ⌉) = n ⌊ n/2 ⌋, where K_⌊ n/2 ⌋, ⌈ n/2 ⌉ is the complete balanced bipartite graph on n vertices. The current asymptotic bounds on F(P_n) stand at 
    1.81 ≤lim_n →∞ (F(P_n))^1/n≤ 2;
 the lower bound was shown in <cit.>.

It is conjectured that F(P_n) = F(K_⌊ n/2 ⌋, ⌈ n/2 ⌉), which is surprising; the complete balanced bipartite graph has many more edges than the path, which is one of the sparsest connected balanced bipartite graphs. Therefore we investigate F(G) for balanced bipartite graphs G more dense than the path but less dense than the complete balanced bipartite graph.

In this paper, we present new bounds on F(G) for various bipartite graphs G, thereby potentially making progress towards determining this value for the path. We show that for all dense enough n-vertex balanced bipartite graphs G, F(G) is near F(K_⌊ n/2 ⌋, ⌈ n/2 ⌉). We also present a smaller family of much sparser bipartite graphs, which have average degree O(log n), for which this growth holds. In comparison, the path graph has average degree approximately 2. We investigate the properties of families of pairwise graph-different permutations where arbitrarily many disjoint vertices are added to a graph. We develop new methods for bounding this quantity for the matching graph and determine its exact value for the 4-vertex matching graph (the graph of 2 independent edges).

In related work, Körner, Malvenuto, and Simonyi <cit.> bounded F(G) for various graphs G with arbitrarily many isolated vertices, and completely determined this value for stars. Cohen and Malvenuto <cit.> presented bounds on F(C_n), where C_n denotes the n-vertex cycle. Their bounds are similar to the current bounds on F(P_n). Körner, Simonyi, and Sinaimeri <cit.> investigated distance graphs, as well as specific graphs G with n vertices such that F(G) does not grow exponentially with n, in contrast to the majority of the results in this field. Frankl and Deza <cit.> looked at a slightly different problem, in which they bounded the maximum number of pairwise t-intersecting permutations, where two permutations are t-intersecting if they share t common positions.

The organization of this paper is as follows. In Section <ref>, we present classes of balanced bipartite graphs for which F is near the upper bound given in (<ref>). In Section <ref>, we investigate the properties of families of pairwise matching-different permutations. We present implications and potential future extensions of our work in Section <ref>.
























§ DENSE BIPARTITE GRAPHS: LOWER BOUNDS








In Section <ref>, we present lower bounds on F for n-vertex bipartite graphs with three different maximum degrees of the bipartite complement; namely, 1, any positive constant, and o(n). In Section <ref>, we present lower bounds for the graph consisting of the union of small disjoint balanced bipartite graphs.



 §.§ Bipartite Graphs with Specified Maximum Degree of Complement


It was shown in <cit.> that F(P_n) ≤n ⌊ n/2 ⌋; from their proof it immediately follows that F(K_a, n-a) = n  a. The following trivial lemma shows that this upper bound applies to all bipartite graphs.


If G is a subgraph of H, then F(G) ≤ F(H).


Any pair of G-different permutations must also be H-different by definition; therefore any family of pairwise G-different permutations is also pairwise H-different.



If G is subgraph of K_a,n-a, then F(G) ≤n  a.


Because it is conjectured that the upper bound in Corollary <ref> is tight for the n-vertex path, it is natural to try to show that this bound is tight for other classes of non-complete bipartite graphs. We present such a class of graphs in the following result.

Let G(n, a) be the graph obtained by removing a maximal matching from K_a,n-a. (By this definition, G(n, n/2) is the crown graph on n vertices.) We use induction on n and a to determine F(G(n,a)) for all n and a in the below theorem.


For all nonnegative integers a ≤ n,

    F(G(n,a)) =
     
    1     n < 3 
    n  a    n ≥ 3.




If n < 3, there are at most 2 vertices in G(n, a), so the graph does not have any edges by definition. Therefore no two permutations are G(n,a)-different, so F(G(n,a)) = 1. We now assume that n ≥ 3.
It suffices to show that F(G(n,a)) ≥n  a, as F(G(n,a)) ≤n  a by Corollary <ref>. We prove the result by induction. For the base case, note that for any nonnegative integer n, F(G(n,0)) = F(G(n,n)) = 1 = n  0 = n  n. This is because G(n,0) and G(n,n) both have no edges, so no two permutations are G(n,0)-different or G(n,n)-different. Additionally, F(G(3,1)) = F(G(3,2)) = 3 = 3  1 = 3  2. This is because G(3,1) and G(3,2) each have 3 vertices and 1 edge, so it suffices to show that F(H) ≥ 3, where H is a graph with vertices labeled 1,2,3 and with an edge between 1 and 2. The 3 permutations

    1     2     3 
    
    3     1     2 
    
    2     3     1

are pairwise H-different, so F(H) ≥ 3, and therefore F(H) = 3.
For the inductive step, assume n > 3, 0 < a < n, and F(G(n-1, d)) = n-1  d for all 0 ≤ d ≤ n-1. It follows that G(n,a) is not an empty graph, so let x and y be vertices in the first and second subsets of G(n,a) respectively such that there is an edge between x and y. If x is removed from G(n,a), the resulting graph is either G(n-1,a-1) or a supergraph of G(n-1,a-1). Likewise, if y is removed from G(n,a), the resulting graph is either G(n-1,a) or a supergraph of G(n-1,a). Then by the inductive hypothesis, there exists a family of at least F(G(n-1,a-1)) permutations of V(G(n,a)) - {x} that are pairwise G(n,a)-different, and there exists a family of at least F(G(n-1,a)) permutations of V(G(n,a)) - {y} that are pairwise G(n,a)-different; let these families be ℱ_x and ℱ_y respectively. Let ℱ be the family that consists of the union of x concatenated to all elements of ℱ_x and y concatenated to all elements of ℱ_y. Then ℱ is pairwise G(n,a)-different, so 
    F(G(n,a)) ≥ |ℱ| = |ℱ_x| + |ℱ_y| = F(G(n-1,a-1)) + F(G(n-1,a)).
 By this induction, F(G(n,a)) = n  a for n ≥ 3, as n  a = n-1  a-1 + n-1  a= F(G(n-1,a-1)) + F(G(n-1,a)).


Therefore for all n ≥ 3, there exist non-complete bipartite graphs on n vertices that are subgraphs of K_a,n-a for which the upper bound of n  a is exactly equal to F. However, the graphs G(n,a) considered in the above theorem are such that the maximum degrees of their bipartite complements are 1. As the path is much more sparse, we want to extend this result to apply to graphs with larger maximum bipartite complement degree. We make the following definition in order to consider such graphs. 

Let F(n, a, Δ) be the minimum value of F(G) over all n-vertex bipartite graphs G that are subgraphs of K_a,n-a, such that the maximum degree of the bipartite complement of G is Δ.

We can now generalize Theorem <ref> as follows.


For all nonnegative integers n, a, and Δ such that n ≥ 2 Δ and Δ≤ a ≤ n - Δ, 
    F(n, a, Δ) ≥n - 2 Δ a - Δ.



We show the result by induction on n and a, just as in Theorem <ref>. For the base case, it suffices to note the trivial observation that F(n, Δ, Δ) ≥ 1 and F(n, n - Δ, Δ) ≥ 1 for all n ≥ 2 Δ.
For the inductive step, let n > 2 Δ. Assume that for all Δ≤ d ≤ n - 1 - Δ, 
    F(n-1, d, Δ) ≥n - 1 - 2 Δ d - Δ.
 It remains to be shown that for any Δ < a < n - Δ, 
    F(n, a, Δ) ≥n - 2 Δ a - Δ.
 Let G be any bipartite graph with n vertices that is a subgraph of K_a,n-a, such that the maximum degree of the bipartite complement of G is Δ. We show that 
    F(G) ≥ F(n-1, a-1, Δ) + F(n-1, a, Δ),
 as then it would follow that 
    F(G) ≥n - 1 - 2 Δ a - 1 - Δ + n - 1 - 2 Δ a - Δ = n - 2 Δ a - Δ
 by the inductive hypothesis.
First, note that G has more than 2 Δ vertices, so it must have at least one subset with more than Δ vertices, and therefore, because Δ is the maximum degree of the bipartite complement graph, G must have at least one edge. Let this edge connect vertices x and y in the first and second subsets respectively. Removing a vertex from a graph cannot increase the maximum degree of the complement graph. Therefore, F(G - {x}) ≥ F(n-1, a-1, Δ) and F(G - {y}) ≥ F(n-1, a, Δ). It follows by definition that there exist pairwise G-different families ℱ_x and ℱ_y of permutations of V(G) - {x} and V(G) - {y} respectively such that |ℱ_x| ≥ F(n-1, a-1, Δ) and |ℱ_y| ≥ F(n-1, a, Δ). Let ℱ be the family of permutations of V(G) consisting of all permutations in ℱ_x concatenated to x and all permutations in ℱ_y concatenated to y. Then ℱ is pairwise G-different by construction, so 
    F(G) ≥ |ℱ| = F(n-1, a-1, Δ) + F(n-1, a, Δ).








For all nonnegative integers n and Δ such that n ≥ 2 Δ, 
    F(n, ⌊ n/2 ⌋, Δ) ≥ 2^-2 Δn ⌊ n/2 ⌋.



It is easy to see by expanding the binomial coefficient that 

    F(n, ⌊ n/2 ⌋, Δ)    ≥n - 2 Δ⌊ n/2 ⌋ - Δ
       ≥ 2^-2 Δn ⌊ n/2 ⌋.



Although the lower bound in Theorem <ref> does not quite reach the upper bound given in Corollary <ref>, it comes within a constant factor of the upper bound for balanced bipartite graphs when Δ is a constant, as shown in Corollary <ref>. This constant factor is due to the difficulty of finding sufficient base cases for the induction on n and a for large Δ. Although for many Δ better base cases are easily found (as in Δ = 1), it is difficult to find general base cases for all Δ.

Because lim_n →∞1/nlog_2 n ⌊ n/2 ⌋ = 1 by Stirling's formula, the function F(K_⌊ n/2 ⌋, ⌈ n/2 ⌉) = n ⌊ n/2 ⌋ grows exponentially on the order of 2^n. We therefore remain primarily interested in showing that F grows on the order of 2^n for various classes of balanced bipartite graphs, and thereby showing that the upper bound on F of n ⌊ n/2 ⌋ is met asymptotically. We now use Corollary <ref> to show that F(n, ⌊ n/2 ⌋, Δ) grows on the order of 2^n if Δ = o(n).




    lim_n →∞1/nlog_2 F(n, ⌊ n/2 ⌋, o(n)) = 1.



First note that 

    lim_n →∞1/nlog_2 F(n, ⌊ n/2 ⌋, o(n))
       ≤lim_n →∞1/nlog_2 F(K_⌊ n/2 ⌋, ⌈ n/2 ⌉) = 1

by Stirling's formula. It therefore suffices to show the opposite inequality to prove a lower bound of 1. By Corollary <ref>, 

    lim_n →∞1/nlog_2 F(n, ⌊ n/2 ⌋, o(n))
       ≥lim_n →∞1/nlog_2 ( 2^-2 · o(n)n ⌊ n/2 ⌋) 
       ≥lim_n →∞1/nlog_2 n ⌊ n/2 ⌋ + lim_n →∞1/nlog_2 2^-2 · o(n)
       = 1 - lim_n →∞2 · o(n)/n
       = 1.


This theorem is particularly interesting because it presents a very large class of graphs such that any graph G in this class has the property that F(G) is near 2^n. However, as Δ = o(n), these graphs are relatively dense. In the next section we present specific but much sparser graphs G for which F(G) is near 2^n.



 §.§ Union of Small Dense Balanced Bipartite Graphs


In this section we show that F grows on the order of 2^n for graphs consisting of the union of small complete balanced bipartite graphs. 
We first present the following well-known lemma, which provides a method for placing lower bounds on F(G) for graphs G composed of disjoint subgraphs. An equivalent result is shown in <cit.>, but we present the proof as it is related to future proofs in this paper.



Let G be the union of disjoint graphs G_1 and G_2. Then F(G) ≥ F(G_1) · F(G_2).


Let ℱ_1 = {π_1, …, π_F(G_1)} and ℱ_2 = {σ_1, …, σ_F(G_2)} be families of pairwise G_1-different and G_2-different permutations respectively of maximum size, so that |ℱ_1| = F(G_1) and |ℱ_2| = F(G_2). Then let ℱ be the family of permutations consisting of π_i concatenated to σ_j for all 1 ≤ i ≤ F(G_1) and 1 ≤ j ≤ F(G_2). Then ℱ is G-different, as for any two permutations π_i_1σ_j_1 and π_i_2σ_j_2, if i_1 ≠ i_2, π_i_1 and π_i_2 are G-different; otherwise j_1 ≠ j_2 and σ_j_1 and σ_j_2 are G-different. Therefore F(G) ≥ |ℱ| = F(G_1) · F(G_2).


Intuitively, if F(G_1) ≈ 2^|V(G_1)| and F(G_2) ≈ 2^|V(G_2)|, then F(G_1 + G_2) ≈ 2^|V(G_1)| + |V(G_2)| = 2^|V(G_1 + G_2)| by Lemma <ref>. Because we want to find bipartite graphs G for which F(G) ≈ 2^|V(G)|, this idea is very useful, and forms the basis of the theorem below.


Let B(n,k(n)) be the balanced bipartite graph of order n consisting of the union of k(n) disjoint balanced complete bipartite graphs, each of order ⌊ n/k(n) ⌋ or ⌈ n/k(n) ⌉. If 
    k(n) = O ( n/log_2 n) ,
 then 
    lim_n →∞1/nlog_2 F(B(n,k(n))) = 1.



For some given n, let k = k(n), B = B(n,k(n)), and let the k disjoint subgraphs of B be B_1, …, B_k with orders n_1, …, n_k respectively. By Lemma <ref>, 
    F(B) ≥∏_i=1^k F(B_i) = ∏_i = 1^kn_i ⌊ n_i / 2 ⌋.
 The right side can be expanded by Stirling's formula, which is easily applied to show that there exists a positive constant l for which 
    x ⌊ x/2 ⌋≥ l ·2^x/√(x)
 holds for all positive integers x. (The actual value of l is not relevant to us, but it is easily bounded.) Then, as ∑_i=1^k n_i = n, and by the AM-GM inequality,

    F(B)    ≥∏_i = 1^kn_i ⌊ n_i / 2 ⌋≥∏_i = 1^k l ·2^n_i/√(n_i) 
    = l^k · 2^n/√(∏_i = 1^k n_i)
       ≥l^k · 2^n/√(( n/k)^k)
    = l^k · 2^n/2^k/2log_2 ( n/k)
       =  l^k · 2^n - k/2log_2 ( n/k).

Therefore 

    F(B(n,k(n))) ≥ l^k(n)· 2^n - k(n)/2log_2 ( n/k(n)).

If k(n) = O(n / log_2 n), it is easily verifiable from (<ref>) that 
    lim_n →∞1/nlog_2 F(B(n,k(n))) ≥ 1.
 The opposite inequality is trivial as B(n,k(n)) is bipartite.


Note that the proof of Theorem <ref> holds even if the k(n) disjoint balanced complete bipartite graphs have different orders; however, the union is sparsest when the disjoint subgraphs are near in order.

Theorem <ref> provides an n-vertex bipartite graph B(n,k(n)) with maximum degree O(log_2 n) such that F(B(n,k(n))) grows on the order of 2^n, or more formally, such that F(B(n,k(n))) = 2^(1-o(1))n. This graph is the sparest balanced bipartite graph we currently know with this property.




§ FAMILIES OF PAIRWISE MATCHING-DIFFERENT PERMUTATIONS









In Section <ref>, we primarily dealt with relatively dense bipartite graphs G such that F(G) was near 2^n. Now we examine very sparse bipartite graphs. The most prominently studied of these is the path; improvements on the lower bound on F(P_n) were made in <cit.>. In this paper we investigate F for the matching graph on n vertices, which we denote M(n). (We will assume n to be even whenever referencing M(n) in this section.) As the matching is a subgraph of the path, any lower bounds on F(M(n)) would also apply to the n-vertex path. Additionally, the matching consists of the union of n/2 disjoint edges, giving it a special structure relating to Lemma <ref>.

We first generalize the function F and show how the generalization is related to the original function.


Let F_b (G) be the maximum size of a family of pairwise G-different permutations of the vertices of G with an additional b blank spaces.

Here a blank space can be thought of as an isolated vertex added to G. For example, consider the family ℱ shown below.

    1     2     * 
        1     2 
    
    2     *     1

We say ℱ is family of 3  pairwise M(2)-different permutations of the vertices of M(2) with 1 blank space; the blank space in each permutation is denoted by *' and simply serves as a placeholder. By this definition, it is clear that F_b (G) ≤ F_c (G) if b ≤ c for any graph G. We now extend Definition <ref> to account for families of permutations with unlimited blank spaces; an equivalent definition was made in <cit.>.

For any graph G, assign each element of V(G) to a unique natural number. Let two infinite permutations of ℕ be G-different if at some position their corresponding elements are both assigned to vertices in G and form an edge in G. Then let F_∞(G) be the maximum size of a family of pairwise G-different infinite permutations of ℕ.

Körner, Malvenuto, and Simonyi <cit.> showed that for any graph G on n vertices, 

    F_∞ (G) ≤ (χ(G))^n,

where χ(G) denotes the chromatic number of G. Therefore, for graphs with finitely many vertices, F_∞ (G) is finite, so it follows that there exists a sufficiently large constant b for which F_b (G) = F_∞ (G). (For example, it is easy to verify that b = n (χ(G))^n satisfies this equation.) We can therefore think of F_∞ (G) as the maximum size of a family of pairwise G-different permutations of the vertices of G with arbitrarily many blank spaces, rather than in terms of infinite permutations of the natural numbers.

If G(n) is a graph defined for all positive integer n, then let 
    ρ_b(G) = lim sup_n →∞1/nlog_2 F_b(G(n)),
 and let ρ(G) = ρ_0(G). (In this paper G(n) will usually be the first n vertices of an infinite graph, as is the case with M(n).) Therefore ρ_b (G) measures the asymptotic behavior of F_b(G(n)). Although it may seem that F_∞ (G(n)) should be much larger than F(G(n)), the following two lemmas show that for certain graphs G(n) such as the matching graph M(n), ρ(G) and ρ_∞ (G) are equal. Very similar results were shown in <cit.> for the path; we present a generalization of these proofs below.


If ℱ is a family of permutations of the vertices of some graph G with any number of blank spaces (or with no blank spaces), let H_ℱ, G be the graph whose vertices are the permutations in ℱ and whose edges are all pairs of permutations σ, π∈ℱ such that σ and π are G-different.

Note that if ℱ is pairwise G-different, then H_ℱ, G is complete, or equivalently, α(H_ℱ, G) = 1.



If ℱ is a family of G_0-different permutations of the vertices of G_0 with unlimited blank spaces, then ρ(G) ≥1/|V(G_0)|log_2 |ℱ|, where G(n) consists of the union of n/|V(G_0)| copies of G_0, for all n which are divisible by |V(G_0)|.

We omit the proof of this lemma, which is similar to the proof of Lemma <ref>. A nearly identical result is shown in <cit.>, which is specific to the path but easily generalizable.















Let G(n) be a graph of order n defined for all positive n such that G(n_1) + G(n_2) is a subgraph of G(n_1 + n_2). If either ρ(G) or ρ_∞ (G) exists (that is, either of their limits exist and is not ∞), then both values exist and ρ(G) = ρ_∞ (G).


Clearly if ρ_∞ (G) exists, then ρ(G) exists and ρ_∞ (G) ≥ρ(G), as F_∞ (G(n)) ≥ F(G(n)) for all n. We now show by contradiction that if ρ(G) exists, then ρ_∞ (G) exists and ρ(G) ≥ρ_∞ (G). Assume that ρ(G) exists and is not ∞, but that ρ_∞ (G) > ρ(G) or that ρ_∞ (G) = ∞. Then, in both of these cases, there exists an N such that there is a family ℱ of pairwise G(N)-different permutations of V(G(N)) with unlimited blanks, where 1/Nlog_2 |ℱ| > ρ(G). However, by assumption the union of k copies of G(N) is a subgraph of G(k N) for all positive integers k. Therefore, ρ(G) ≥1/Nlog_2 |ℱ| by Lemma <ref>, which is a contradiction.


Lemma <ref> shows that ρ_∞ (M) = ρ(M). As M(n) is bipartite, ρ(M) ≤ 1, so ρ_∞ (M) ≤ 1. Therefore F_∞ (M(n)) grows exponentially on the order of at most 2^n. This bound was improved in <cit.>, where it was shown that √(3)^n ≤ F_∞ (M(n)) ≤ 2^n. The upper bound of 2^n was shown as part of the more general result that F_∞ (G) ≤ (χ(G))^|V(G)|, where χ(G) denotes the chromatic number of G. We use a different approach for bounding F_∞ (M(n)); we first bound α(H_ℱ, M(2)) for families ℱ of permutations of the vertices of M(2), then we use this result to bound α(H_ℱ, M(n)) for larger n. This approach helps determine F_∞ (M(n)) for small n and provides a slightly stronger upper bound on F_∞ (M(n)) for all n (better than 2^n by a constant factor). We also present some interesting constructions of families ℱ with relatively good upper bounds on α(H_ℱ, M(n)); these results mark progress towards potentially improving the lower bounds on F_∞ (M(n)).



Let ℱ be a family of permutations of the vertices of M(2) with b blank spaces, and let c = b + 2 be the length of the permutations in ℱ. Then 
    α(H_ℱ, M(2)) ≥2^c-2/2^c - 2· |ℱ|.



Assume the vertices of M(2) are labeled 1 and 2, so that all permutations in ℱ consist of 1, 2, and c-2 blanks. We first observe that an independent set in H_ℱ, M(2) cannot contain permutations π and σ such that π(j) = 1 and σ(j) = 2 for some position j. Therefore, an independent set I in H_ℱ, M(2) is characterized by a string s of 1's and 2's of length c. A permutation π∈ℱ is in I only if π(j) = s(j) for every position j at which π does not have a blank space.

There are 2^c possible labelings of the c positions with 1's and 2's, but 2 of these (all 1's and all 2's) always correspond to empty independent sets. Therefore let I_1, …, I_2^c-2 be the 2^c-2 independent sets of maximal size in H_ℱ, M(2) corresponding to strings of 1's and 2's of length c. Each permutation π∈ℱ belongs to exactly 2^c-2 of these independent sets, as each of the c-2 blank spaces in π may be labeled 1 or 2 in the string s. Therefore 
    ∑_i=1^2^c-2 |I_i| = 2^c-2· |ℱ|.
 It follows by the pigeonhole principle that there exists some k for which 
    |I_k| ≥2^c-2/2^c - 2· |ℱ|.





    α(H_ℱ, M(2)) > 1/4· |ℱ|.



The inequality in Lemma <ref> is only significantly stronger than that in Corollary <ref> for families of permutations that are very short in length. It is therefore desirable to be able to consider families of permutations with as few blank spaces as possible. The following lemma shows that families of permutations with sufficiently many blank spaces can be condensed to equivalent families with fewer blank spaces.



Let ℱ = {π_1, π_2, …, π_p} be a family of p permutations of the vertices of M(2) with b blank spaces, and let c = b + 2 be the length of each permutation in ℱ. If p < c  2, then there exists a family ℱ' = {π_1', π_2', …, π_p'} of p permutations of the vertices of M(2) with b-1 blank spaces such that H_ℱ, M(2) is a subgraph of H_ℱ', M(2).


There are c  2 pairs of positions j_1, j_2 in the permutations in ℱ. If p = |ℱ| < c  2, then by the pigeonhole principle there must be some pair of positions j_1, j_2 (1 ≤ j_1 < j_2 ≤ c) such that each permutation in ℱ has a blank space in at least one of these positions. Then for each π_i, let π_i' be the permutation consisting of π_i with the entry at position j_2 removed, and let π_i'(j_1) take on the value of whichever of π_i(j_1) or π_i(j_2) is not a blank space. In other words, position j_2 was merged into position j_1 for each permutation π_i to obtain π_i'. Then ℱ' = {π_1', π_2', …, π_p'} satisfies the desired properties.


We now apply Lemma <ref> and Lemma <ref> to determine the value of F_∞ (M(4)) and to improve the existing upper bound on F_∞ (M(n)) by a constant factor.



F_∞ (M(4)) = 9.


We show that a family of 10 permutations of V(M(2)) with unlimited blank spaces cannot be M(2)-different. Specifically, it suffices to show that there is no family ℱ_1 of 10 permutations of the vertices of M(2) with unlimited blanks such that α(H_ℱ_1, M(2)) ≤ 3 and |E(H_ℱ_1, M(2))| > 22. To see this, label the vertices on the two edges in M(4) (1, 2) and (3, 4) respectively. Then, for any family ℱ = {π_1, …, π_10} of 10 permutations of the vertices of M(4) with unlimited blanks, let ℱ_1 = {σ_1, 1, …, σ_1, 10} be the family ℱ with all 3's and 4's replaced by blank spaces, and let ℱ_2 = {σ_2, 1, …, σ_2, 10} be the family ℱ with all 1's and 2's replaced by blank spaces. By this definition, (π_i_1, π_i_2) ∈ E(H_ℱ, M(4)) if and only if (σ_1, i_1, σ_1, i_2) ∈ E(H_ℱ_1, M(2)) or (σ_2, i_1, σ_2, i_2) ∈ E(H_ℱ_2, M(2)). Therefore, if S ⊆{1, …, 10} and if {σ_1, i : i ∈ S} is an independent set in H_ℱ_1, M(2), then {σ_2, i : i ∈ S} must be a clique in H_ℱ_2, M(2) in order for H_ℱ, M(2) to be complete; the same applies for independent sets in H_ℱ_2, M(2) and cliques in H_ℱ_1, M(2). Because the largest clique in both H_ℱ_1, M(2) and in H_ℱ_2, M(2) has order at most F_∞ (M(2)) = 3, the independence number of both graphs must be 3 (it cannot be less than 3 by Lemma <ref>). Furthermore, the complete graph on 10 vertices has 45 edges, so either H_ℱ_1, M(2) or H_ℱ_2, M(2) must have at least 23 edges in order for H_ℱ, M(2) to be complete.

As 5  2 = 10, it is only necessary to consider families with at most 3 blank spaces by Lemma <ref>. The case of 0 blanks is trivial; for families ℱ_1 of permutations of the vertices of M(2) with 1 blank space, note that by Lemma <ref>, 
    α(H_ℱ_1, M(2)) ≥2^3 - 2/2^3 - 2· 10 = 10/3 > 3.
 If ℱ_1 has 3 blank spaces, then the permutations have length 5, so each of the 10 pairs of positions j_1, j_2 must correspond to the 1 and the 2 of some permutation in ℱ_1; otherwise the family could be condensed by Lemma <ref>. Therefore for each 1 ≤ j ≤ 5, exactly 4 permutations in ℱ_1 do not have a blank space at position j. Among these 4 permutations, there are at most 2 · 2 = 4 pairs of M(2)-different permutations (π_i_1, π_i_2) which correspond to edges in H_ℱ_1, M(2). Therefore H_ℱ_1, M(2) has at most 5 · 4 = 20 edges. The only remaining case is when the permutations have 2 blank spaces. We used a brute force computer search for this case, and found that no 10 permutations of the vertices of M(2) with 2 blanks has independence number 3.



F_∞ (M(n)) < 9 · 2^n-4 for even n > 4.


It suffices to show that for even n > 4, F_∞ (M(n)) < 4 · F_∞ (M(n-2)). To show this, we use the same method of separating out the independent edges that we used in Theorem <ref>. Label the vertices of the n/2 edges in M(n) (1,2), (3,4), …, (n-1,n). Let ℱ be some family of pairwise M(n)-different permutations of the vertices of M(n) with unlimited blank spaces. Let ℱ_1 be the family ℱ with all numbers other than 1's and 2's replaced with blank spaces, and let ℱ_2 be the family ℱ with all 1's and 2's replaced with blank spaces. (By this definition, ℱ_1 contains permutations of the vertices of M(2) and ℱ_2 contains permutations of the vertices of M(n-2)). Because any independent set in H_ℱ_1, M(2) must correspond to a clique of equal size in H_ℱ_2, M(n-2), the clique number of H_ℱ_2, M(n-2) must be at least α(H_ℱ_1, M(2)) > 1/4· |ℱ|. By definition, F_∞ (M(n-2)) is an upper bound on the clique number of H_ℱ_2, M(n-2), so 
    F_∞ (M(n-2)) > 1/4· |ℱ|.
 As this inequality holds for all pairwise M(n)-different families ℱ of permutations of the vertices of M(n) with unlimited blanks, it must be that 
    F_∞ (M(n-2)) > 1/4· F_∞ (M(n)).
 


To conclude this section we present results which were motivated by the problem of improving the lower bound on F_∞ (M(n)). We first observe that there exist families ℱ of permutations of the vertices of M(2) such that α(H_ℱ, M(2)) is very close to 1/4· |ℱ|. Specifically, for any integer c ≥ 2, let 𝒜_c be the family of the c(c-1) distinct permutations of the vertices of M(2) with c-2 blank spaces. Let s be a string of 1's and 2's of length c characterizing an independent set I in H_𝒜_c, M(2). If s has x 1's and y 2's, then |I| = xy by the definition of ℱ. Therefore the size of the largest independent set in H_𝒜_c, M(2) is α(H_𝒜_c, M(2)) = ⌊ c/2 ⌋·⌈ c/2 ⌉. It follows that 

    lim_c →∞α(H_𝒜_c, M(2))/|𝒜_c| = lim_c →∞⌊ c/2 ⌋·⌈ c/2 ⌉/c(c-1) = 1/4.

This construction shows that the bound in Lemma <ref> is nearly optimal. We now apply the ideas in Lemma <ref> and in (<ref>) to get an interesting result.

Let ℱ be a family of p pairwise M(n)-different permutations of the vertices of M(n) with unlimited blank spaces, and once again label the vertices of the edges in M(n) (1,2), (3,4), …, (n-1, n). Let ℰ_2, ℰ_4, …, ℰ_n be defined such that ℰ_k = {σ_k, 1, …, σ_k, p} consists of the family ℱ with all non-blank entries other than k-1 and k replaced by blank spaces in each permutation. Let ℱ_0 = {π_0, 1, …, π_0, p} be a family of p empty permutations (or permutations of the vertices of M(0)). It follows that H_ℱ_0, M(0) is empty and α(H_ℱ_0, M(0)) = p. Then let ℱ_2 = {π_2, 1, …, π_2, p} be defined so that π_2, j consists of π_0, j concatenated to σ_2, j, and in general, let ℱ_k = {π_k, 1, …, π_k, p} be such that π_k, j consists of π_k-2, j concatenated to σ_k, j. (This definition is such that H_ℱ_n, M(n) = H_ℱ, M(n).) Note that for any positive even k and for any indices i_1 and i_2, (π_k, i_1, π_k, i_2) ∈ E(H_ℱ_k, M(k)) if and only if either (π_k-2, i_1, π_k-2, i_2) ∈ E(H_ℱ_k-2, M(k-2)) or (σ_k, i_1, σ_k, i_2) ∈ E(H_ℰ_k, M(2)). It follows by Lemma <ref> that for any independent set I in H_ℱ_k-2, M(k-2), there exists an independent set I' in H_ℱ_k, M(k), which is a subset of I, such that |I'| > 1/4· |I|. Therefore α(H_ℱ_k, M(k)) > 1/4·α(H_ℱ_k-2, M(k-2)), so by induction 
    α(H_ℱ_k, M(k)) > p/2^k
 for all positive even k. As shown in (<ref>), for k = 2 there exist families ℱ_2 (namely, 𝒜_c for large c) such that α(H_ℱ_2, M(2)) is arbitrarily close to 1/2^k = 1/4. However, if p ≈ 2^n, then α(H_ℱ_k, M(k)) must be approximately p/2^k for all 1 ≤ k ≤ n, as α(H_ℱ_n, M(n)) = 1. More generally, if ρ_∞(M) ≥1/2log_2 a for some constant a, then there must exist families ℰ_2, …, ℰ_n such that their corresponding families ℱ_0, …, ℱ_n satisfy α(H_ℱ_k, M(k)) ≈p/a^k/2 and n ≈log_√(a) p (loosely speaking). Below, we present a construction which partially answers this question by providing families ℰ_2, …, ℰ_l such that for certain a > 3, α(H_ℱ_k, M(k)) is within a constant factor of p/a^k/2 for 0 ≤ k ≤ l, where l grows logarithmically as a function of p (but slower than log_√(a) p). We later explain how this result could potentially be extended to improve the lower bound on ρ_∞ (M).



Let 𝒜 be some family of permutations of the vertices of M(2) with unlimited blank spaces, and let p be some positive integer. Let l = 2 ·⌈log_|𝒜| p ⌉. Then there exists a family ℱ_l of p permutations of M(l) such that 
    α(H_ℱ_l, M(l)) ≤ P · a^l/2,
 where P is the least power of |𝒜| not less than p and a = α(H_𝒜, M(2))|𝒜|.


Let q = |𝒜| and let 𝒜 = {A_1, A_2, …, A_q}. For even k where 2 ≤ k ≤ l, let ℰ_k = {σ_k, 1, …, σ_k, P} consist of the pattern

    A_1, …, A_1_q^k/2-1, A_2, …, A_2_q^k/2-1 ⋯ A_q, …, A_q_q^k/2-1

repeated P/q^k/2 times. Let ℱ_k = {π_k, 1, …, π_k, P} be defined the same before: π_k, j = π_k-2, j σ_k, j.

It remains to be shown that α(H_ℱ_l, M(l)) = P · a^l/2. We first observe that any independent set with indices I_l of maximum size in H_ℱ_l, M(l) is constructed in the following manner. Let I_0 = {1, …, P} represent the indices of the independent set π_0, 1, …, π_0, P in H_ℱ_0, M(0). For each 2 ≤ k ≤ l, choose some independent set ℬ_k in H_𝒜, M(2) of size α(H_𝒜, M(2)). Then let I_k = {j ∈ I_k-2 : σ_k, j∈ℬ_k}. By this construction, α(H_𝒜, M(2)) out of every q elements of I_k-2 will be in I_k. Therefore by induction, as I_k is of maximum size by assumption, 
    α(H_ℱ_k, M(k)) = |I_k| = P · (α(H_𝒜, M(2)) / q)^k/2 = P · a^k/2
 for all even 0 ≤ k ≤ l.





§ CONCLUSION







In this paper, we develop new methods for bounding the maximum size of a family of pairwise graph-different permutations for various bipartite graphs. For specific non-complete bipartite graphs G with vertex subsets of size a and b, we show that the upper bound on F(G) of F(K_a,b) is tight. We show that if G(n) is any balanced bipartite graph on n vertices with minimum degree n/2 - o(n), then F(G(n)) grows on the same exponential order as F(K_⌊ n/2 ⌋, ⌈ n/2 ⌉) when n →∞. We also show that this growth is achieved for certain much sparser balanced bipartite graphs. We present several new bounds on F_∞ for the matching graph M(n). Specifically, we determine the exact value of F_∞ (M(4)), and improve the upper bound on F_∞ (M(n)). Our new methods and bounds make potential progress towards determining the value of F(P_n).







§ ACKNOWLEDGEMENTS

We would like to thank Dr. Tanya Khovanova for her helpful comments and suggestions on the paper. We would also like to thank the MIT PRIMES program for providing us with the opportunity to perform this research.



ieeetr

