We introduce a novel linear-algebraic planarity criterion based on the number of spanning trees. We call a matrix an incidence submatrix if each row has at most one 1, at most one -1, and all other entries zero. Given a connected graph G with m edges, we consider the maximum determinant \mathsf{maxdet}(G) of an m \times m matrix [M|N], where M is the incidence matrix of G with one column removed, over all incidence submatrices N of appropriate size, and define its excess to be the number of spanning trees in G minus \mathsf{maxdet}(G). Given a disconnected graph, we define its excess to be the sum of the excesses of its connected components. We show that the excess of a graph is 0 if it is planar, and at least 18 otherwise. This provides a “certificate of planarity” of a planar graph that can be verified by computing the determinant of a sparse matrix and counting spanning trees. Furthermore, we derive an upper bound on the maximum determinant of an m \times m matrix [M|N], where M and N are incidence submatrices. Motivated by this bound and numerical evidence, we conjecture that this maximum determinant is equal to the maximum number of spanning trees in a planar graph with m edges. We present partial progress towards this conjecture. In particular, we prove that the \mathsf{maxdet}(⋅) value of any subdivision of K_{3, 3} or K_5 is at most that of the best planar graph with the same number of edges.
@article{bu2024planarity,title={Planarity via Spanning Tree Number: A Linear-Algebraic Criterion},author={Bu, Alan and Pan, Yuchong},journal={SIAM J. Discrete Math.},year={2024},publisher={Society for Industrial and Applied Mathematics},}
Branching Contractions Revisited: Tighter Running Time Bound on Simple Unweighted Hypergraphs
@unpublished{pan2024branching,title={Branching Contractions Revisited: Tighter Running Time Bound on Simple Unweighted Hypergraphs},author={Pan, Yuchong and Wang, Joshua T.},year={2024}}
On High-Value and High-Flow Cycles at Basic Feasible Solutions of the Subtour Elimination Relaxations for the Symmetric and Asymmetric Traveling Salesman Problems
Melkonian [Inf. Process. Lett., 101 (2007)] introduced the concepts of high-value and high-flow cycles at basic feasible solutions of the subtour elimination relaxation for the asymmetric traveling salesman problem (ATSP), in hope of designing a constant-factor approximation algorithm for ATSP. We show that high-value cycles do not always exist at basic feasible solutions of the subtour elimination relaxations for the symmetric and asymmetric traveling salesman problems. Furthermore, we exhibit a reduction from the thin tree conjecture to the existence of a constant-flow cycle, the former of which is at least as hard as finding a constant-factor approximation algorithm for ATSP itself.
@unpublished{goemans2024high,title={On High-Value and High-Flow Cycles at Basic Feasible Solutions of the Subtour Elimination Relaxations for the Symmetric and Asymmetric Traveling Salesman Problems},author={Goemans, Michel X. and Pan, Yuchong},year={2024},}
2023
A Counterexample to Box-Half-Integrality of the Intersection of Crossing Submodular Flow Systems
@unpublished{goemans2023counterexample,title={A Counterexample to Box-Half-Integrality of the Intersection of Crossing Submodular Flow Systems},author={Goemans, Michel X. and Pan, Yuchong},year={2023},}
2021
Optimization Problems on Network Flows with Degree Constraints
In a vertex-capacitated directed graph with sources and sinks, we would like to concurrently route demands from the sources to the sinks. This model has many applications in the real world. However, conditions in the reality usually incur new side constraints to this general model. For instance, the next-hop routing in Internet protocol (IP) networks requires each router to have one single next destination, called the next hop, for each incoming packet destined to an IP address. A flow with this property is said to be confluent. If this constraint is relaxed to allow d next destinations at each vertex, then such a flow is said to be d-furcated. In general, side constraints concerning bounded out-degree of each vertex give rise to network flows with degree constraints. Such constraints contribute to simplicity of resulting network flow models. Given a network flow model, several optimization problems can be asked. For instance, how the demands can be routed so that the flow does not exceed the capacity at each vertex too much? Another natural question is to find a subset of the demands with the maximum amount which can be routed subject to the vertex capacities. In this thesis, we survey algorithms that find approximate solutions close to optimum values within theoretically guaranteed factors.
@masterthesis{pan2021optimization,title={Optimization Problems on Network Flows with Degree Constraints},author={Pan, Yuchong},year={2021},type={Undergraduate Honours Thesis},school={University of British Columbia},}
