I live with four people, who thankfully don't spend much time on maths.se. We decided this year that we'd do a Secret Santa. We can represent the arrangement of who's buying for whom using a directed graph $G = (V,E)$. $V = \{\alpha,\beta,\gamma,\delta,\varepsilon\}$ is our vertex set, and $(u,v) \in E$ iff $u$ is buying a present for $v$. We decided to produce this graph by writing our names on bits of paper, shuffling them around, and each picking one out. If the name we draw is invalid, then we draw another piece of paper. Our validation rules were as follows:
- No participant shall buy for themselves - so $(v,v) \notin E$
- $\delta$ and $\varepsilon$ are a couple, who will be buying for each other separately from the secret santa. Rather than waste edges, they've decided to render each other invalid, so $(\delta,\varepsilon) \notin E$ and $(\varepsilon, \delta) \notin E$
- Each person buys for exactly one other person - so $deg_{in}(v) = deg_{out}(v) = 1$
I know who I bought for. Can I deduce the entire structure of the graph from this information?
I can reduce the graph to four possible structures, posted as a partial answer, which already gives me a pretty large amount of information. I don't think I can get any more information about the state of the graph simply from knowing who I'm buying for, but I have some information on the order in which names were drawn, and know that we never had to reshuffle.
Based on information provided by the draw, how would I find the probability of each of the possible Secret Santa arrangements?
Partial answer - the possible graphs of giving:
In these graphs, the nodes labelled $\delta/\varepsilon$ or $\varepsilon/\delta$ will take on different values, leading to four possible graphs. In both situations, $\alpha$ has the most natural information. Can more be gained from knowledge of the draw?
Since $\epsilon$ and $\delta$ are, for all intents and purposes, symmetric, there is no way of knowing which of the two is giving you a gift unless you ask one of them and they decide to disclose it to you since the person they are giving it to isn't you (I don't know how strict or confidential your Secret Santa is). But, on to probability:
You have a simple directed graph with 5 edges and 5 vertices that are not necessarily connected. Thus there are without any preconditions, ${20\choose 5}$ possible graphs. However, we know one of the edges (specifically $\alpha\to\beta$) and that two edges are impossible. Moreover, we know that $\beta$ must have degree $2$. The chance of $\beta\to\alpha$ is precluded by the fact that this would force $\epsilon\to\delta$ or vice-versa, while $\beta\to\gamma$ can't happen because then we would have $\delta\leftrightarrow\epsilon$. So we have a $\frac{1}{2}$ chance of $\beta\to\delta$ and $\epsilon$ each. Let $\beta\to X$, where $X\in\{\delta,\epsilon\}$. Then, with your restrictions, $X\to\alpha$ and $\gamma$ are the only possibilities, again with a $50/50$ chance of each. Whether $X$ maps to $\alpha$ or $\gamma$ uniquely determines the graph, as your depictions illustrate. All this is to say, each of the four graphs you present is equally likely assuming that your draw was random.