On the number of a SDRs of a valued (t,n)-family

Dawei He, Changhong LüarXiv 2010 · DOI · arXiv

Abstract

A system of distinct representatives (SDR) of a family $F = (A_1, \dots, A_n)$ is a sequence of $n$ distinct elements $(x_1, \dots, x_n)$ such that $x_i \in A_i$ for all $i$. Hall’s Theorem provides the necessary and sufficient condition for the existence of at least one SDR: the union of any $k$ sets must contain at least $k$ elements. This paper investigates $(t, n)$-families, where the union of any $k$ sets contains at least $k + t$ elements. We settle a long-standing conjecture by G.J. Chang regarding the minimum number of SDRs, denoted $M(t, n)$, for $t \ge 3$. By generalizing the problem to "valued" $(t, n)$-families, we provide a complete proof of the lower bound and characterize the unique families that achieve this minimum.

Introduction

The study of Systems of Distinct Representatives (SDRs) is a cornerstone of combinatorial design and graph theory. While Hall's Marriage Theorem (1935) established the conditions for $N(F) \ge 1$, subsequent research has focused on finding lower bounds for the number of SDRs when families possess additional "slack."

In 1989, G.J. Chang introduced the concept of a $(t, n)$-family. A family $F = (A_1, \dots, A_n)$ is a $(t, n)$-family if for every non-empty subset of indices $I \subseteq \{1, \dots, n\}$: $$\left| \bigcup_{i \in I} A_i \right| \ge |I| + t$$

Chang determined the minimum number of SDRs, $M(t, n)$, for $t=0, 1, 2$ and conjectured a general formula for $t \ge 3$. Although a proof was attempted in 1992, it was later found to contain a fundamental error regarding the application of permanents. This paper provides the definitive proof of Chang's conjecture.

Methodology: The Valued Generalization

The primary challenge in proving $M(t, n)$ for higher values of $t$ via standard induction is that the $(t, n)$ property is often lost when reducing the problem to smaller sub-families. To overcome this, we introduce the concept of a valued $(t, n)$-family.

In a valued family, each set $A_i$ is associated with a non-negative integer $a_i$. The family is considered a valued $(t, n)$-family if for any $k$ sets, their union contains at least $k + t$ elements, and specifically, the sets are structured such that we can account for the "base" size $a_i$ of each set. This generalization allows for a more robust inductive step: by transforming a standard $(t, n)$-family into a valued one, we can track how the removal of an element affects the remaining structure without losing the underlying slack $t$.

Structural Analysis and Transformations

Our proof relies on two key structural concepts:

  1. Exclusive and Saturated Pairs: We analyze the relationships between elements and sets to identify "exclusive pairs"—elements that appear in a highly restricted number of sets.
  2. Family Transformations: We demonstrate that if a family is not the conjectured minimal family $\bar{F}$, it can be transformed (e.g., by shifting an element from one set to another) to strictly decrease the number of SDRs. This iterative reduction proves that the minimum must occur at $\bar{F}$.

Key Results

Settlement of Chang’s Conjecture

We confirm that for any $(t, n)$-family, the minimum number of SDRs is given by the formula: $$M(t, n) = \sum_{j=0}^{t} \binom{t}{j} \binom{n}{j} j!$$

This formula represents the number of ways to choose $j$ elements from a "slack" set of size $t$ and $n-j$ elements from the sets themselves, accounting for all possible permutations.

The Valued Case

For the more general valued $(t, n)$-family with valuations $(a_1, \dots, a_n)$, we derive the minimum number of SDRs as: $$U'(t, n, a_1, \dots, a_n) = \sum_{j=0}^{t} \left[ \binom{t}{j} j! \sum_{1 \le i_1 < \dots < i_{n-j} \le n} a_{i_1} \dots a_{i_{n-j}} \right]$$

Uniqueness

Beyond finding the value, we prove that the family $\bar{F}$ is the unique family (up to isomorphism) that achieves this minimum. Any deviation from the structure of $\bar{F}$—where sets overlap in a specific, saturated manner—necessarily results in a higher number of SDRs.

Discussion and Conclusion

By introducing valuations, we successfully bridged the gap left by previous attempts. The "fatal mistake" in earlier literature stemmed from an incorrect comparison of permanents; our inductive approach avoids this pitfall by focusing on the structural properties of the families themselves.

While this work settles the question of the minimum number of SDRs, the maximum number remains an open and significantly more complex problem. The maximum is tied to the theory of permanents of (0,1)-matrices and likely requires different combinatorial tools. Additionally, while our proof holds for $t \ge 2$, future work could seek a unified framework that treats $t=1$ as a natural consequence rather than a boundary case.

Summary updated

Abstract

A system of distinct representatives (SDR) of a family $F = (A_1, \cdots, A_n)$ is a sequence $(x_1, \cdots, x_n)$ of $n$ distinct elements with $x_i \in A_i$ for $1 \le i \le n$. Let $N(F)$ denote the number of SDRs of a family $F$; two SDRs are considered distinct if they are different in at least one component. For a nonnegative integer $t$, a family $F=(A_1,\cdots,A_n)$ is called a $(t,n)$-family if the union of any $k\ge 1$ sets in the family contains at least $k+t$ elements. The famous Hall's Theorem says that $N(F)\ge 1$ if and only if $F$ is a $(0,n)$-family. Denote by $M(t,n)$ the minimum number of SDRs in a $(t,n)$-family. The problem of determining $M(t,n)$ and those families containing exactly $M(t,n)$ SDRs was first raised by Chang [European J. Combin.{\bf 10}(1989), 231-234]. He solved the cases when $0\le t\le 2$ and gave a conjecture for $t\ge 3$. In this paper, we solve the conjecture. In fact, we get a more general result for so-called valued $(t,n)$-family.
BibTeX
@misc{he2010number,
  author = {Dawei He and Changhong Lü},
  title = {{On the number of a SDRs of a valued (t,n)-family}},
  year = {2010},
  eprint = {1007.2029},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1007.2029},
}
Figure