Skip navigation
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, Maria
Holzman, 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

Files in This Item:
File Description SizeFormat 
TRETIAK-SIVAN-THESIS.pdf232.18 kBAdobe PDF    Request a copy


Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.