Triangle coloring in random graph Given $m$ persons (men and women) and $n$ balls, each person randomly selects $3$ balls. Once all of them complete the selection process, we color the balls with $2$ colors, white and black, such that (1) for any set of three balls selected by a same man, there are at least $2$ black balls, and (2) for any set of three balls selected by a same woman, there are at least $2$ white balls. The problem is to design a coloring algorithm satisfying the above constraints. Is it related to some known problem in random graphs? Is there a threshold $n_0$ that once $n\ge n_0$, the algorithm will succeed w.h.p.? We may allow reselection of balls but we want to limit the reselection to $O(1)$ times.
 A: It appears to me that you are essentially asking two questions that are independent:
Question 1.  Is there an algorithm that finds a solution should one exists?
Question 2.  Under what conditions on $M$ and $N$, there is guaranteed to be a solution w.h.p.?
I can exactly answer the first question, and provide some empirical data for the second one. Let me start with reformulation this problem.
Reduction to 2-SAT
A 'random selection' can be seen as a random instance of a constraint satifaction problem (CSP) with $n$ constraints and $m$ variables: Each ball corresponds to a Boolean variable $v_i$ that can attain one of two values (black or white), for simplicity I will use True (or 1) for black and False (or 0) for white. Each person corresponds to a constraint that involves 3 variables, the constraints then requires that at least two of the three variables are True or at least two of them are False. These two variant constraints can be formulated in a CNF as:
$$
    \beta(x, y, z) \equiv (x \vee y) \wedge (y \vee z) \wedge (z \vee x)
$$
and
$$
    \upsilon(x, y, z) \equiv (\neg x \vee \neg y) \wedge (\neg y \vee \neg z) \wedge (\neg z \vee \neg x)
$$
This essentially allows us to formulate an instance of this CSP as an instance of 2-SAT.
An efficient algorithm
2-SAT is a well-known tractable problem, so there is a lot of efficient algorithms. One can certainly be found in Schaefer's classification of Boolean CSPs (Schaefer, 1978), but any algorithm for 2-SAT will work here.
The key property of this problem, and consequently of your problem is that it can be solved by checking local consistency. More precisely, if there is a system $\mathcal F$ of partial solutions defined on at most 3-element subsets of variables (i.e., every $f\in \mathcal F$ is a function $f\colon X \to \{0, 1\}$ where $\lvert X\rvert \leq 3$ and $f$ satisfies any constraints on its values (the latter only applies if $X$ is the set of balls chosen by someone) such that:

*

*for each $X$ with at most 3 elements, there is $f \in \mathcal F$ with $\operatorname{dom} f = X$,

*for each $Y \subset X$ and $f \in \mathcal F$ with $\operatorname{dom} f = X$, the restriction of $f$ onto $Y$ belongs to $\mathcal F$, i.e., $f|_Y \in \mathcal F$; and

*for each $Y \subset X$ adn $g \in \mathcal F$ with $\operatorname{dom} g = Y$, there is $f\in \mathcal F$ with $\operatorname{dom} f = X$ and $f|_Y = g$.

(such a system is said to be consistent). Intuitively this consistency just requires that any of the function in $\mathcal F$ defined on $X$ is consistent with some other function defined on any given $Y$. One consistent system can be found by starting with the system of all partial solutions and inductively removing functions that invalidate (2) or (3). If at any point, we remove the last function with some domain $X$, there is no solution. This gives an algorithm which decides whether there is a solution.
For finding a solution there are a few tricks: one trick is to guess a value for some variable and repeat the decision algorithm to decide whether there is a solution using this value and repeat. This might require a few guesses for each value, but in your case any $f$ from an above system will extend to a full solution. (See Section 5.3 of (Barto, Krokhin, Willard, 2017) for more insights about 2-SAT.)
A test
To give some light on the second question, note that there is a lot of research on random CSP instances, see e.g. (Coja-Oghlan, 2009). Based on my quick search, it seems that these usually have a sharp transition in terms of the parameter $m/n$, i.e., there is a constant $\alpha$ s.t. if $m/n < \alpha$, then there is no solution w.h.p., and if $m/n > \alpha$, there is a solution w.h.p.. The below data might give some insights on what the threshold might be.
To get some idea about this threshold (if there is one), I used a SAT-solver (PicoSAT developped by Armin Biere) to empirically check what are chances that a random instance of the given CSP is satisfiable. Though this SAT solver is able to solve general SAT which is way harder than 2-SAT, none of my implementations of a theoretically more efficient algorithm were able to provide a solution in comparable times.
The code that I used is this:
import pycosat
import random

def man(x, y, z):
    yield (x, y)
    yield (y, z)
    yield (x, z)

def woman(x, y, z):
    yield (-x, -y)
    yield (-y, -z)
    yield (-x, -z)

def generate_instance(m, n):
    for i in range(n):
        scope = random.sample(range(1, m+1), 3)
        relation = random.choice((man, woman))
        yield from relation(*scope)

def test(m, n, repeat=100):
    positive = 0
    for i in range(repeat):
        solution = pycosat.solve(generate_instance(m, n))
        if solution != "UNSAT":
            positive += 1
    return positive

Roughly, the functions man and woman provide the translation to 2-SAT, and generate_instance(m, n) generates a random instance with m balls and n people. The probability of genders of these people is 50/50. The function test then generates and tests 100 random instances and counts the number of solvable ones.
Using this code I tested different fractions $n/m$ for $m \in \{10, 100, 1000, 10000\}$. The graph below shows the fraction of solvable ones. Each line corresponds to a fixed value of $m$. Looking at the graph, I think it is unlikely that a random instance with $n > m/3$ will have a solution. Hope this helps!

A: Not quite a full answer, but an observation. This problem gets easier to solve the larger the vat is. If there are only 3 balls in the vat then it is impossible to find such a coloring. If on the other hand there are $N^2$ balls in the vat where $N$ is the number of people then this should be easy for a random instance; each person will have 3 balls not shared with anyone else.
EDIT The threshold is $\theta(N)$, here $N$ is the number of people. If the number of balls is $(3+\epsilon)N$ then putting an edge between a man and a woman iff they share a ball, iff there exists a good coloring, then there exists a good coloring within each component. But then it looks like whp the size of the largest components would be only $O(\log N)$, using a similar line of reasoning that the largest cc in a graph $G$ drawn according to ER$(N,\frac{1-a}{N})$ is $O(\log N)$ for all $a \in \Omega(1); 0<a \le 1$.
If the number of balls is $cN$ with $c$ is some small constant say $c \le .1$, then with high probability there is no such coloring. Informally, let $S$ be the set of balls, and let $S_W$ be the set of balls picked by the women and let $S_M$ the set of balls picked by the men. Then $S_W, S_M$, and $S$ are almost the same set, with most balls picked about the same number of times by each gender. So then for there to be such a coloring, about 2/3 of the balls in $S_W$ would have to be white and about 2/3 of the balls in $S_M$ would have to be black. But then this makes impossible to simultaneously satisfy both conditions as $S_M$ and $S_W$ have such high-overlap.
