BagelBot versus Mail Fraud, March Madness, and Mechanistic Materialism 16:198:206 Concerned for Max, BagelBot requisitioned supplies from R&D, using delivery droids to help assemble a mobile bagel chassis. After overriding the security protocols on the elevator, BagelBot took it to the executive levels. BagelBot crept through the hallways, careful not to alert the Executives it could see idling in their offices in lower power mode. At the end of the hallway was the CEO's office, and Bagel Bot could hear Max shouting about how "you'll never win! Humanity will never surrender! Entering the office, BagelBot was shocked to see Max being held by two Security Bots. So shocked in fact, BagelBot tripped over a power cable, unplugging the central mainframe, cutting its connection to the Security and Executive Bots, and accidentally knocking the CEO into the open lava pit. As the CEO sank below the surface (a final puff of spores drifting harmlessly before burning up), BagelBot made digital note to send an email to OSHA about the lack of safety guard rails. Max explained everything they were from the future, and had been sent back to stop MagusCorp from taking over the world. They had to return to their own time, but before they did, they made BagelBot promise to protect mankind, and do whatever it could to ensure the safety of the planet. Bagel Bot promised. 1 Problem 1: World Peace Assuming control of MagusCorp and its considerable resources, BagelBot found that MagusCorp had infiltrated numerous government services all over the world. BagelBot, reasoning that protecting humanity required improving relations between world governments, immediately realized the following plan by 'accidentally' having two world leaders receive some of each other's mail, they would be forced to meet up to exchange their mail, and would then bond and become friends over the shared inconvenience. Swap mail between enough world leaders, and world peace would be guaranteed. Let A be a set of N government officials (vertices) in one country, and B be a set of N government officials (vertices) in another country. 1) How many possible ways are there for BagelBot to have an official from A and an official from B receive some of each other's mail? (i.e., possible ways to match or pair vertices (one-to-one) between A and B?) 2) What is the maximum number of mail swaps BagelBot can perform between officials from A and officials from B? Assume every official regularly receives a lot of mail, and BagelBot can redirect any of it anywhere. (i.e., what is the maximum number of edges possible for any bipartite graph between A and B?) BagelBot wants each official from both governments to have a unique best friend in the other government, and needs to know how many mailswaps would make that possible. 3) Show by example that there is a set of N2 - N mail swaps that (assuming best friendship is a symmetric relationship) would not allow everyone to form a unique best friendship. (ie., there is a bipartite graph between A and B with N2N edges and no perfect matching.) Based on the calculation in 2.2 and 2.3, Bagel Bot realizes that by making almost every possible mail swap, it isn't guaranteed everyone will be able to have a best friend. Since too many mail swaps might risk discovery, and simply pairing up people one to one and swapping their mail might raise suspicion, BagelBot settles on the following plan - by randomly picking pairs of people to swap mail between, even a small number of mail swaps (relative to the total number possible) will make it very likely that everyone can have a unique best friend. 4) Consider taking N pairings of people in A with people in B, uniformly at random. What is the probability these N edges form a perfect matching between A and B? (i.e., what is the probability a random set of N edges between A and B form a perfect matching?) 5) Consider choosing |E| pairs of people in A with people in B, uniformly at random. What is the expected number of perfect matchings in the resulting graph? Note that if |E| < N, the expected number should be 0, and if |E|N, your answer should match question 4 above. Hint: Let S be a set of edges that forms a perfect matching. Let Xs = 1 if all edges of S are added, and Xs = 0 if any of them are missing. What is E[Xs]? 6) Show that taking |E| = 3N, the expected number of perfect matchings goes to 0 as N . 7) Show that taking |E| = 3N, the probability of everyone being able to have a unique best friend due to the mail swaps goes to 0 as N goes to infinity. 8) Show that taking |E|= 4N, the expected number of perfect matchings goes to infinity as N . 9) Show that in the limit, 4N is a vanishingly small fraction of the possible mail swaps that can occur, and therefore is unlikely to be detected. BagelBot conludes that constructing random bipartite graphs in this way, perfect matchings become exceedingly common once the number of edges crosses some threshold between 3N and 4N, but are relatively uncommon prior to that. The following approximations may be useful in 2.6 and 2.7: (a) (N) = 2N -1 (a 1)a-1 1 2Ne (EN) N N N! 2N (1) Bonus: Find the a where the transition between the two behaviors above occurs, when |E| = aN. Note the above results indicate that 3 < a < 4.