DIMACS
DIMACS REU 2023

General Information

me
Student: Molly MacDonald
Mentor: Swee Hong Chan
School: University of Notre Dame
E-mail: mmacdon6@nd.edu
Project: Sorting Probability for Linear Extensions

Project Description

My project is motivated by the 1/3-2/3 Conjecture which states that in every finite partially ordered set that is not totally ordered, there exists a pair of elements x and y with the property that at least 1/3 and at most 2/3 of the linear extensions of the partial order place x earlier than y. This has become one of the more famous conjectures in set theory and while no one has succeeded to prove such a result for all partially ordered sets, there are partial results for posets with certain properties.

For a poset P = (X, ≤),
δ (P) = min x, y ∈ X | P[L(x) ≤ L(y)] - P[L(y) ≤ L(x)] |
where L is a linear extension of P chosen uniformly at random. The 1/3-2/3 Conjecture hypothesizes that δ (P) ≤ 1/3 for all posets P. My mentor, Professor Chan, has proven that for the Catalan Poset Pn, which is defined as a product of a chain with 2 elements and with n element, δ (Pn) = O(n-5/4). My goal is to prove that for P3, n, which is defined as a product of a chain with 3 elements and with n element, δ (P3,n) = O(1/n)

Weekly Log

Week 1:
I spend the short week of week one reading Professor Swee Hong Chan's paper on the sorting probability of the Catalan Poset. In this paper, he proved that δ (Pn) = O(n-5/4), and so I read the paper very carefully in order to possibly apply his methodology to my own problem.
Week 2:
I began this week by listening to my peers' presentations on their respective projects and giving my presentation. My mentor and I then met afterwards to go over things I did well during the presentation and things I could improve on for next time. I then spent the first half of the week finishing up reading Professor Chan's paper.
I then began my own work. My first challenge was to find a combinatorial way to represent P[L(3,c) ≤ L(1,a)] where (1,a) corresponds to the ath element of the first row and where (3,c) corresponds to the cth element of the third row. I ended up utilizing the hook length formula for a Standard Young Tableaux, and I made some progress.
Week 3:
During the third week, there was a series of presentations on graph algorithms, and I attended a few of them. This week I also found the formula for P[L(3,c) ≤ L(1,a)]. Professor Chan then gave me a side-quest having to do with Stanleys inequality
Week 4:
During week 4, I proved that the inequality in Professor Chan's side-challenge held for (P3,n). I then returned to my main project. I let f(c) = P[L(3,c) ≤ L(1,a)], and I calculated f(c) - f(c+1) because one way to prove that (P3,n) = O(1/n) is to show that f(c) - f(c+1) = O(1/n). Once calculated, I used Stirling's formula to approximate the factorials in the formula.
Professor Chan and I met on Friday and we were ultimately only able to show that f(c) - f(c+1) = O(1/sqrt(n)). While this was not our desired result, this lemma would prove to be useful later on.
Week 5:
This week, I took a look at Rn(h, z):= P[L(3,h-z) ≤ L(1,h)]. The work I did during week four proved that Rn(h, *) = O(1/sqrt(n)). This week, the goal was to examine Rn(h, z) - Rn(h+1, z). I was able to show that Rn(h, z) - Rn(h+1, z) is equal to a double sum consisting of binomial coefficients.
Week 6:
At the beginning of the week, Prof. Chan and I were able to show that Rn(h, z) - Rn(h+1, z) = O((n-2h)/sqrt(n)). Thus, we had proven the two lemma's necessary to show (P3, n) = O(n-5/4)
I was unfortunately sick for the remainder of the week.
Week 7:
During the beginning of the week, I was still recovering from being sick. Once I felt well again, I began typing up the lemmas in latex and working through the details Prof. Chan and I had initially glossed over.
Week 8:
This week, we gave our presentations! I spend the first half of the week preparing my slides. On Thursday, half of the students gave their presentations, and I spent the remaining half of the day practicing giving my presentation. On Friday, I gave my presentation. I think it went well, and the other students said it was very understandable.
Week 9:
I spent the beginning of this week continuing to type up my work. I finished writing a report summarizing my overall experience, I finished this website, and I completed a draft of my paper. On Friday, I will be flying back home. For the remaining two months before school starts back up, I will be working to finish a final draft of my paper along with proving the result not just for P3, n, but for Pd, n.