General Information

Project Description

Graphs are becoming larger and larger every day, but the vertices of interest to us (called terminals) are potentially few. The paradigm of vertex sparsification explores the power and limit of compressing large graphs into smaller ones, while preserving important information, specifically cut and flow structures, with respect to terminals.
In this project, we will study a fundamental characterization problem (for cuts): Given a set T of terminals and a (2^T-2)-dimensional vector π whose coordinates are indexed by proper subsets of T, decide if there is a graph G that contains T, such that for all subsets S of T, π_S equals the value of the min-cut in G separating S from T\setminus S. We will also explore related questions concerning flow structures.

Weekly Log

Week 1:

My focus for this week was on understanding the foundational concepts and significant previous works in the study of mimicking networks and vertex sparsifiers in graph theory. This included an in-depth analysis of the characterization of multiterminal flow networks and the principles underlying the construction of mimicking networks, especially for networks with bounded treewidth. This involved reviewing seminal works by Hagerup, Katajainen, Nishimura, and Ragde, who introduced the concept of mimicking networks, and subsequent advancements by other researchers that improved the upper and lower bounds on the size of these networks. These studies provided a solid theoretical framework for the practical implications of constructing smaller, more efficient mimicking networks for large-scale graphs with multiple terminals​ .

Week 2:

More reading this week: specifically, I focused on the inequalities presented by Chaudhuri et al. for sets of terminals of order k=3,4,5. I studied how these inequalities can be applied to characterize terminal cuts in different network configurations. Additionally, I explored Zihan et al.'s generalization of Chaudhuri's findings using linear programming and Khan et al's findings about the convex cone(ality?) of the set of type vectors for a given k, which provided a broader framework for understanding terminal cuts in more complex graphs. I then made steps towards developing a system of inequalities for the 6 terminal case.

Week 3:

Completed the necessary background reading and leveraged Chaudhuri's work and the submodularity lemma toward developing a robust set of inequalities that can precisely describe the behavior of terminal cuts in graphs with 6 terminals. The focus was on ensuring that these inequalities are tight and accurately reflect the minimum cut values for various subsets of terminals for 31-dim type-vectors. Additionally, I developed an understanding of how to transform cut problems into dual distance problems by leveraging continuous optimization methods.

Week 4:

In the fourth week , I continued to build on the foundational inequalities developed in previous weeks. I focused on refining the system of inequalities for the 6-terminal case, ensuring their tightness and applicability to various network scenarios. This involved extensive mathematical derivations and proofs to validate the correctness of the proposed inequalities. Additionally, I explored different methods for simplifying the computations involved in these derivations, aiming to make the process more efficient and scalable for larger networks.

Week 5:

I delved even deeper into advanced techniques for analyzing cut functions, did more reader in digraph theory, pondered my Diestel the works. A significant highlight of this week was a discussion with Martin Loebl, who shared his research on fair claims resolution, critical good distribution, and multi-criteria envy-free allocations. I also investigated how to optimize cut functions using dual distance problems and continuization, furthering my understanding of their theoretical underpinnings. 

Week 6:

On Tuesday, I presented my research to the NYU Combinatorics REU, sharing my findings and methodologies with peers and mentors. This presentation provided valuable feedback and insights that helped refine my approach. Concurrently, I continued my research on the system of inequalities for the 7 and 8-terminal case, incorporating the feedback received and addressing any identified gaps or weaknesses. This week marked a pretty big milestone in my research, as I got to pretty effectively synthesize and communicate what I've been doing so far this summer, which honestly helped give me a better understanding of any holes in my thinking and what I could do next

Week 7:

Week seven included a field trip to Nokia Bell Labs, which was an enriching and inspiring experience. We had the opportunity to tour the facilities and attended a panel of researchers who discussed their findings in areas such as image generation. The researchers also highlighted Nokia Bell Labs as a place where you can pursue your own personal projects while working on assigned research, emphasizing the freedom and support available for innovative ideas. It was amusing and inspiring to see names like "Hamming" and "Shannon" on plaques during our tour of the first floor, reminding us of the profound contributions made by these pioneers. The anechoic chamber, in particular, was a fascinating experience, sparking my interest in sensor deprivation and its various applications. Despite the excitement of the trip, my primary focus remained on my research, where I made further advancements in deriving tight inequalities and began drafting a comprehensive report to document my findings and methodologies, setting the stage for final presentations. I would talk more about the Grad student panel that also happened this week, but I fear that this summary is already disproportionately long compared to the others.

{"mode":"full","isActive":true,"isUserDisabled":false}