Partially perfect hash functions for intersecting families

Consider a large network with unknown number of nodes. Some of these nodes coordinate to perform tasks. The number of such coordination groups is also unknown. The only information about the network available is that any two coordinating groups share at least $t$ nodes. To complete a particular task in a day, at least $p$ nodes of the corresponding coordinating group must get different time slots out of the $r$ available slots per day. Is there a way of estimating the number of days required such that every coordinating group gets at least one day where it can complete the task? As it turns out, this problem is a special case of \textit{partially} perfect hash functions for intersecting families.


Definition 1 A hash function h from [n] into [b] is said to be a partially p-perfect with respect to a subset S ⊆ [n] provided that |h(S)| ≥ min(p, |S|). A collection H of functions from [n] into [b]
is called a (b, k)-family of partially p-perfect hash functions provided that for each subset S ⊆ [n] of size k, there is a function h ∈ H which is partially p-perfect with respect to S.
denotes a complete r-uniform hypergraph on n vertices. Then, we have the following lower bound on t (see [2] for details).
See Radhakrishnan [2] for related problems and results. The connection between t and a minimum cardinality (b, k)-family of partially p-perfect hash function is immediate.
We study an interesting variation of partially p-perfect hash functions for intersecting families. A hypergraph is called t-intersecting if every pair of hyperedges share at least t vertices. The set of hyperedges of a t intersecting hypergraph is called as a t-intersecting family. (G, p, b) system for a hypergraph G is a collection H of partially p-perfect hash functions such that for each hyperedge e ∈ G, there is a function h ∈ H which is partially p-perfect with respect to e.

Definition 2 A
Let λ(G, p, b) denote the minimum cardinality of a (G, p, b) system where G is a hypergraph. Let λ(t, p, b) denote the maximum of λ (G, p, b) where G is a t-intersecting family. In this paper, we study the parameter λ(t, p, b) in detail.

Main result
In Section 2.1, we prove the following result.
The theorem is interesting in the sense that provided b > (p − 1)(t + 1), every t-intersecting hypergraph G has a (G, p, b) system of size at most 2. However, when b ≤ (p − 1)(t + 1), the study of the behaviour of λ(t, p, b) remains open.

Bounds on λ(t, p, b)
The fact that λ(t, p, b) ≥ λ(t + 1, p, b) follows from the fact that any t + 1-intersecting family is also tintersecting. Moreover, λ(t, p, b) is non-increasing with increasing b as well, i.e. λ(t, p, b) ≥ λ(t, p, b + 1) due to the same containment argument. Further, λ(0, p, b) = ∞ -if no restriction on the minimum size of intersection between hyperedges is there, then λ(0, p, b) must depend on the ground set size as evident from Equation 2.

PROOF. To prove the lower bound, let
be a hash function. It is easy to see that at least two elements of V get the same hash value and hence, one hyperedge in G is not partially 2-perfect. For the upper bound, consider any 1-intersecting hypergraph G on the ground set V . Pick an hyperedge e such that there is no hyperedge e ′ with e ′ ⊂ e. Let h 1 : V → {c1, c2} be a hash function such that each element of e get the hash value c1, and each element not in e get the hash value c2. From the restriction on e, it follows that for every e ′ e, h 1 is partially 2-perfect. For hyperedge e, we can choose another hash function. PROOF. In what follows we prove that λ(2, 2, 2) = 1 and from non-increasing property of λ(t, p, b) with increasing t, the proof follows. Consider the following greedy algorithm for obtaining the hash function h 1 , given a ground set V and a t-intersecting family G. Assign the vertices with hash value c1 unless making it c1 makes every vertex in some e ∈ G receiving the same hash value -in this case assign the vertex with hash value c2. For the sake of contradiction, assume that every vertex in e gets the same hash value. Due to our algorithm, all vertices of e gets the same hash value c2. Let x be the last vertex getting hash value c2 belonging to e. The algorithm assigns x with hash value c2 due to the fact that all other vertices of some other hyperedge e ′ containing x received c1. As the hypergraph is 2-intersecting, e ∩ e ′ = {x, y}, for some other vertex y. From the above argument, y must have received the hash value c1 which contradicts our assumption that every vertex in e gets the same hash value. This completes the proof.  1, p, b). But what happens if we modify parameters t and p simultaneously? In fact the monotonicity property changes, which we state in the following theorem.
PROOF. Consider a t-intersecting hypergraph G with minimum cardinality of a partial (G, p, b) system exactly λ(t, p, b). We make it k-uniform by adding extra vertices. Our first task is to get a t + 1-intersecting hypergraph, which we can achieve by adding a vertex v to the vertex set V (G) and adding v to every hyperedge e ∈ E(G). Let the new hypergraph be G ′ . Note that λ(G ′ , p + 1, b) is a lower bound for λ(t + 1, p + 1, b). So, all we need to show is λ(G ′ , p + 1, b) ≥ λ(t, r, p) in order to complete the proof. Let x = λ(G ′ , p + 1, b). Let H ′ be a (G ′ , p + 1, b) system of size x. We construct another family H of partial (G, p, b) system by keeping the same hash values as in This bound implies a rather strange property of t-intersecting hypergraphs which is given as a corollary below.
So we focus on the cases where t ≥ p − 1. We start our analysis with the case of t = p − 1. Consider a complete k-uniform hypergraph G(V, E), where |V | = k(1 + x), for some 0 < x ≤ 1 and some positive integer i. Assume G is p − 1 intersecting. Consider a hash function h 1 : V → k. The most frequent p − 1 hash values are assigned to at least (p − 1)⌊ k(1+x) k ⌋ = 2p − 2 vertices (let this set of vertices be V 1 ). So for any k ≤ 2p − 2, there exists a hyperedge that is not partially p perfect with respect to h 1 . As a result, at least one more hash function is needed in order to cover that hyperedge. All we need to show now is there exists a p − 1 intersecting complete k-uniform hypergraph on (1 + x)k vertices, where k ≤ 2(p − 1) and 0 < x ≤ 1. Choosing k = 2p − 2, x = 0.5, we get |V | = 3p − 3. Observe that the number of vertices shared between any two hyperedges is at least 2 * (2p − 2) − 3p − 3 = p − 1, hence the hypergraph is p − 1 intersecting. Consequently, we have the following lower bound.
For the general case of t ≥ p, consider a pt-uniform complete hypergraph G. In order to make G tintersecting, we make |V | = 2pt − t. Consider a hash function h 1 : V → 2p − 3. The most frequent p − 1 hash values are assigned to at least 2p−3 ⌉ = ⌈pt + t 2p−3 ⌉ > pt vertices (note that if the hash function is h 1 : V → 2p − 2, then we may not get this guarantee). Consequently, there exist at least one hyperedge that receives at most p − 1 hash values by h 1 , which needs at least one more coloring.

An upper bound
For a fixed 0 < p <1, the p-biased measure of a family F over [n] is µ p (F ) := P r S [S ∈ F ], where the probability over S is obtained by including each element i ∈ [n] in S independently with probability p. Such a set S is called a p-biased subset of [n]. The combined results of Dinur and Safra [3] and Friedgut [4] gives the following theorem.
Theorem 11 Fix t ≥ 1. Let F be a t-intersecting family. For any p < 1 t+1 , the p-biased measure of F is bounded by µ p (F ) ≤ p t .
The following is an easy corollary of the above theorem.
Corollary 12 Fix t ≥ 1. Let F be a t-intersecting family. For any p < 1 t+1 , the probability that a p-biased subset of [n] contains a set S ∈ F is at most p t .
PROOF. Consider a t-intersecting family F and let T = {T ⊆ [n]|F ∈ F and F ⊆ T }. Note that T is tintersecting. Consider a p-biased subset S ⊆ [n] for some p < 1 t+1 . Observe that S contains a set of F if and only if S ∈ T . From Theorem 11, we have µ p (T ) ≤ p t . So, the probability that a p-biased subset of [n] contains a set S ∈ F is at most p t . ✷ We give an upper bound on λ(t, p, b) using the above corollary. The interesting case that remains open is when b ≤ (p − 1)(t + 1) where the above probabilistic method becomes useless. The bottleneck in analysis b > (p − 1)(t + 1) comes directly from its dependence on the measure µ p (F ) given by Theorem 11. Moreover, it is also worthwhile studying the case when b ≤ (p−1)(t+1) taking the size of the hypergraph into consideration.