Please use this identifier to cite or link to this item: http://arks.princeton.edu/ark:/88435/dsp015t34sn665
 Title: Rainbow Fractional Matchings Authors: Tretiak, Sivan Advisors: Chudnovsky, MariaHolzman, Ron Department: Mathematics Class Year: 2021 Abstract: Aharoni, Holzman, and Jiang proved that if 2n color classes each have fractional matching number at least n, then they have a rainbow fractional matching of size n. They showed this result as a special case of a more general theorem for hypergraphs which they proved using a topological approach. We present a combinatorial proof of their result for graphs and a corresponding O(n$$^{3}$$) time algorithm to find a rainbow fractional matching of size n. URI: http://arks.princeton.edu/ark:/88435/dsp015t34sn665 Type of Material: Princeton University Senior Theses Language: en Appears in Collections: Mathematics, 1934-2021