Latest Events
Research seminar by Mr. Yashdeep Singh on Nov 28, 2025 at 12 PM
Title of the talk: Popular Matchings
Date, Time & Venue: Nov 28,2025 at 12 noon on Seminar Room, Dept. of Mathematics
Abstract: Popular matching is a graph-theoretic framework for choosing a “socially preferred’’ matching when vertices rank their possible partners, where one matching is preferred over another if a majority of vertices individually favor it. Such models arise in settings like roommate allocation, student–project assignment, and small-group formation, where agents express preferences over feasible pairings. A matching is called popular if no other matching defeats it in a majority vote.
In the first part of the talk, I will introduce the basic definitions, explain the unpopularity factor, and use small examples to illustrate how majority comparisons work and why a popular matching may fail to exist even in simple graphs. We then move to more general structures, including non-bipartite graphs and 3-uniform 3-partite hypergraphs, which better capture practical allocation scenarios encountered in applications.
In the second part, I will briefly present recent results in these settings. For 3-uniform 3-partite hypergraphs with one-sided preferences, I show that deciding whether a popular matching exists is computationally hard and obtain a bound on how close any matching can be to popularity via the unpopularity factor. For non-bipartite graphs, I show that subcubic and cactus graphs always admit matchings with an unpopularity factor of at most 2, which is optimal.
About the speaker: Mr. Yashdeep Singh is completing his Ph.D. in Computer Science and Engineering at IIT Guwahati under the supervision of Prof. Sushanta Karmakar, working on popular matching problems in non-bipartite graphs and hypergraphs. His research contributions include NP-hardness results and approximation algorithms, with publications in IWOCA, CANDAR, and Concurrency and Computation: Practice and Experience. He also holds an M.Tech. in Computer Science and Engineering from IIT Guwahati and is currently awaiting his Ph.D. defense.
