Seminar Details
Subgraph Complementation and Minimum Rank
- Start Date: April 5, 2023
- Event Start Time: 12:15 PM
- Event End Time: 1:15 PM
- Seminar Series: Graduate Combinatorics Seminar
- Presenter(s): Calum Buchanan - University of Vermont
- Event Location: Mathematics Graduate Student Lounge -- 7th Floor | Rutgers University | Hill Center | Mathematics Department
- Event Additional Info: <p>See: <a href="https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html">https://sites.math.rutgers.edu/~kmg326/GCS/GCS.html</a></p>
- Presentation Type: Stand Alone Presentation
- Abstract:
It is possible to obtain any simple graph G from any other graph H on the same set of vertices V by performing a sequence of subgraph complementations. That is, we can iteratively replace induced subgraphs by their graph complements until we obtain G from H. We ask for the minimum number of subgraph complementations in such a sequence, which can be reduced to finding the minimum number of subgraph complementations needed to obtain G from the graph on V with no edges. Finding this number, which we denote by c2(G), relates closely to the minimum rank problem. We show that c2(G) = mr(G, F2) when mr(G, F2) is odd or when G is a forest; otherwise, mr(G, F2) ≤ c2(G) ≤ mr(G, F2) + 1. We then provide two conditions equivalent to having c2(G) = mr(G, F2) + 1 and give a combinatorial interpretation of mr(G, F2) in this case as well. Finally, the class of graphs G with c2(G) ≤ k is hereditary and finitely defined, and we exhibit the sets of minimal forbidden induced subgraphs for small values of k.
This is joint work with Christopher Purcell and Puck Rombach.