The symmetric difference is the set of elements which are in either of the sets, but not in their intersection. The symmetric difference of the sets $A$ and $B$ is denoted by $A\operatorname {\triangle } B.$
Let $F_1$, $F_2$,…,$F_k$ be finite sets. For simplicity of notation, we let $\triangle_{i=1}^{k}F_i=F_1\triangle F_2 \triangle \cdots \triangle F_k$.
Problem 1. Let $F_1$, $F_2$,…,$F_n(n\ge 3)$ be finite sets such that each set $F_i$ has exactly $5$ elements and $|F_i\cap F_j|\le1$ for $i\ne j$ and $F_i\cap F_j \cap F_k=\varnothing$ for $i\ne j\ne k$. What is the lower bound on $|\triangle_{i=1}^{n}F_i|$?
I guess that $9$ is the answer. Because $F_1\triangle F_2=9$ or $10$. My feeling is that $|\triangle_{i=1}^{l}F_i|\ge |\triangle_{i=1}^{l-1}F_i|$. But it lacks a rigorous derivation.
When we change part of the numerical condition of Problem 1 to more general letters, the following query is posed.
Problem 2. Let $F_1$, $F_2$,…,$F_n (n\ge 3)$ be finite sets such that each set $F_i$ has exactly $m$ elements and $|F_i\cap F_j|\le s$ for $i\ne j$ and $F_i\cap F_j \cap F_k=\varnothing$ for $i\ne j\ne k$. What is the lower bound on $|\triangle_{i=1}^{n}F_i|$?
My feeling is that the Inclusion–exclusion principle can be used, but I have not used it well enough to even answer the above two problems.
The principle of inclusion–exclusion states that for finite sets $A_1, …, A_n$, one has the identity
$$
\left| A_1\cup \dots \cup A_n\right| = \sum_i \left| A_i\right|-\sum_{i<j} \left| A_i\cap A_j\right|+\sum_{i<j<k} \left| A_i\cap A_j\cap A_k\right|-\dots+(-1)^{n+1}\left| A_1\cap \dots \cap A_n\right|.
$$
So is there a nice formula for the symmetric difference on sets like the one above? If there is, maybe my problem will be solved soon, too. Or even change the conditions, we get more general estimates. Maybe upper bounds and so on.
From wiki: https://en.wikipedia.org/wiki/Symmetric_difference.
Suppose $ A=\left\{A_{1},A_{2},\ldots, A_{n}\right\}$ is a multiset and $n\geq 2$. the symmetric difference of a collection of sets contains just elements which are in an odd number of the sets in the collection:
$${\displaystyle \triangle A=\left\{b\in \bigcup A:\left|\{B\in A:b\in B\}\right|{\text{ is odd}}\right\}.}$$
Evidently, this is well-defined only when each element of the union ${\textstyle \bigcup A}$ is contributed by a finite number of elements of $A$.
The number of elements in $\triangle A$, given solely in terms of intersections of elements of $A_i$:
$$ |\triangle A|=\sum _{l=1}^{n}(-2)^{l-1}\sum _{1\leq i_{1}<i_{2}<\ldots <i_{l}\leq n}\left|A_{i_{1}}\cap A_{i_{2}}\cap \ldots \cap A_{i_{l}}\right|.$$
Best Answer
A nice formula for symmetric difference of $n$ sets, is "the set of all elements which appear an odd number of times in total". Since we assume that intersection of any 3 distinct sets is empty, that is equivalent to "the set of all elements which appear in only one of the sets". Note that our condition is that no element appears in more than 2 sets. By $f(n)$ denote minimum cardinality of $F_1 \triangle F_2 \triangle \ldots \triangle F_n$, where $F_k$ meet our conditions.
Problem 1.
We want to make as many elements as possible to appear in exactly 2 sets. We can directly check some initial minima:
I got those numbers by sketching graphs; sets are vertices, and they are connected by edge iff they share an element. Since they can share at most 1 element, this defines a simple graph. Any vertex can be of degree at most 5. Cardinality of symmetric difference is number of unpaired elements, that is for set $F_k$ (being vertex) it is $5 - \deg F_k$. Summing all unpaired elements gave results above.
Fix $n$ and set $k := n \mod 6$. If $k \in \{1, 2\}$ divide sets into $\lfloor n / 6\rfloor$ groups, where first group have $k + 6$ elements, and the rest $6$ elements. We can fill them with elements such that all sets in any group of 6 have empty symmetric difference, and the symmetric difference of the first group have at most $1$ element. So we can make cardinality as not greater than $1$.
If $k \in \{0, 3, 4, 5\}$ divide sets into $\lceil n / 6\rceil$ groups, where first group have $k$ elements (or $6$, when $k = 0$), and the rest $6$ elements. As before, we get that we can get as low as $9$.
So all in all we can always go $9$ or lower. Since for $n=3$ we have that $9$ is actual lower bound, it is the final result.
I think you could prove that $f(n) = n \mod 2$ for $n \geq 6$, but it is unnecessary for this problem.
Problem 2. (not completed)
There exists $N$ such that $f(N) = 0$. So using previous construction, exists a number $M$ such that $f(n) \leq M$, where $M = \max \{f(k)|k \leq 2N\}$. We have that $N \leq m + 1$, since we could restrict ourselves to the case where $|F_i \cap F _j| \leq 1$, and use graph approach as before ($K_{m + 1}$ would do the job).