University of Victoria
Saturday, November 18, 2017
About the Combinatorial Potlatch
The Combinatorial Potlatch is an irregularly scheduled, floating, one-day conference. It has been held for many years at various locations around Puget Sound and southern British Columbia, and is an opportunity for combinatorialists in the region to gather informally for a day of invited talks and conversation. While most who attend work in, or near, the Puget Sound basin, all are welcome. Typically there are three talks given by speakers who are visiting or new to the area, along with breaks for coffee and lunch. Many participants remain for dinner at a local restaurant or pub.
The American Heritage Dictionary defines "potlatch" as: A ceremonial feast among certain Native American peoples of the northwest Pacific coast, as in celebration of a marriage or an accession, at which the host distributes gifts according to each guest's rank or status. Between rival groups the potlatch could involve extravagant or competitive giving and destruction by the host of valued items as a display of superior wealth. [Chinook Jargon, from Nootka p'achitl, to make a potlatch gift.]
This fall's Potlatch is being hosted by the Department of Mathematics at the University of Victoria in Victoria, BC on Saturday, November 18, 2017.
More info, including a history and links to previous Potlatches, is at The Combinatorial Potlatch Home Page.
Schedule
All talks will be held in the Cornett Building, Room B143, with registration and breaks nearby. See the Getting There section for exact locations and directions.
A tentative schedule follows.
- 10:00 AM Registration, Bagels and Coffee
- 11:00 AM Talk: Tinaz Ekim
- 12:00 PM Lunch at Original Joe's
- 2:30 PM Talk: Jephian Lin
- 3:00 PM Cookies, Coffee and Cokes
- 3:30 PM Talk: Bruce Shepherd
- 5:00 PM Happy Hour, Dinner at Bartholomew's Pub
Talks and Abstracts
Tinaz Ekim, Bogazici University, Istanbul
Recent Results on Equimatchable Graphs
A graph is called equimatchable (EQM for short) if every (inclusion-wise) maximal matching of it has the same size. EQM graphs can be seen as the matching counterpart of well-covered graphs defined as graphs having all of their maximal independent sets of the same size and which have been extensively studied in the literature; one can note that a graph is EQM if and only if its line graph is well-covered.
In this talk, we will survey both old and recent results about EQM graphs and point out several research directions. Most attention will be given to structural and algorithmic properties of EQM graphs. Among recent results, we first exhibit an infinite family of forbidden subgraphs, whose existence is rather surprising since the property of being EQM is not hereditary as we will easily observe. Then we consider the stability of the property of being EQM. We call edge-stable equimatchable (ESE for short) those EQM graphs such that the graph obtained by the removal of any edge is still EQM and give a full characterization of ESE graphs. Similarly, we characterize vertex-stable EQM graphs. We also introduce the opposite notion of edge-critical and vertex-critical EQM graphs which are EQM graphs such that the removal of any edge (respectively, any vertex) harms the equimatchability.
Lastly, if time permits, we briefly mention two extensions of the property of equimatchability by defining two new graph parameters that measure how far a graph is from being EQM. The first one, called the matching gap, measures the difference between the sizes of a maximum matching and a minimum maximal matching. The second extension is obtained by introducing the concept of equimatchable sets; a set of vertices in a graph $G$ is said to be equimatchable if all maximal matchings of $G$ saturating the set are of the same size. Noting that $G$ is EQM if and only if the empty set is equimatchable, we define the equimatchability defect of a graph as the minimum size of an equimatchable set in it.
Jephian Lin, University of Victoria
General Spectral Graph Theory: the Inverse Eigenvalue Problem of a Graph
Spectral graph theory usually studies the relations between a graph and a corresponding matrix, which can be the adjacency matrix, the Laplacian matrix, the normalised Laplacian matrix, or other matrices. For each graph $G$, these matrices belong to the family $\mathcal{S}(G)$ of symmetric matrices whose $i,j$-entry with $i\neq j$ is nonzero whenever $\{i,j\}\in E(G)$ and zero otherwise. (Diagonal entries can be either zero or nonzero.) The inverse eigenvalue problem studies the ``general property'' of $\mathcal{S}(G)$ and aims to find all possible spectra appearing in $\mathcal{S}(G)$. We will go through many graph concepts such as the diameter, the domination number, and the graph minor theory, and then discuss their relations to matrices.
Bruce Shepherd, McGill University
Stable Matchings and Extensions
We first review the stable marriage problem where $n$ women are to be matched to $n$ men and where each individual has a strict preference order on people of the opposite sex. A matching (collection of $n$ marriages) is stable if there does not exist a man and woman who want to bail on their current arrangement, as they prefer each other. This problem has had countless applications, most notably to kidney donor programmes and student-class assignment problems. The Gale-Shapley Algorithm is a simple and efficient for solving the stable marriage problem. We then turn to the conflict-free disjoint path problem which was recently introduced in work on confluent flows. We show that this latter problem is a generalization of stable matchings. Moreover, intuition from Gale-Shapely guides us to an algorthm for this more complex problem.
Registration
The Combinatorial Potlatch has no permanent organization and no budget. And we like it that way. Consequently, there are no registration fees because we wouldn't know what to do with them. You are on your own for meals and lodging, and the sponsoring institutions provide facilities, food for the breaks and sometimes a little support for speakers' travel. So expressions of appreciation to the speakers and the hosts are preferred and especially encouraged. Thanks.
Getting There
Victoria is on Vancouver Island, so a ferry or float plane will likely be part of your travel plans. Specific information about travel from Seattle or Vancouver can be found here. And this page has detailed listings for various services. Float planes and the Black Ball ferry (the MV Coho from Port Angeles) arrive in the harbour in central Victoria, and so place you within walking distance to many hotels. The morning run of the MV Coho should give you time to come directly to the talks if you take a taxi after clearing immigration.
The University of Victoria Campus is located away from the central downtown area. So if you wish to overnight where there are more hotels and restaurants, you will need to arrange transportation to/from the campus (bus, taxi). The number 4 bus departs from near the Marriott and goes to the campus.
If you are driving, Parking Lot 4 is suggested as your best option. $2 for the day.
Talks will be held in room B143 of the Cornett Building, inside the ring road on the campus map.
Lodging
No special arrangements have been made for lodging. Here are some suggestions. Many hotels in Victoria offer a UVic rate, which attendees can ask about, but we recommend also checking online to make sure that's the best available rate.
- The James Bay Inn
- It is a 10-20 minute walk to the bus to UVic, unless you transfer.
- Helm's Inn
- Same general area as James Bay Inn. Maybe a bit closer to town.
- Best Western Plus Inner Harbour
- Close to ferry landing.
- Days Inn Victoria
- Close to ferry landing.
- Marriott Inner Harbour
- Convenient public bus to campus.
- Chateau Victoria
- Close to Marriott, but cheaper.
- Swans Suite Hotel
- Lots of character, but try not to get a room right over the pub.
- Delta Hotels by Marriott Victoria Ocean Pointe Resort
- On the waterfront.
Dining and Happy Hour
You are encouraged to join other conference participants at the various meals and other events we have planned for the day. Details are below.
Lunch: Original Joe's, 1654 McKenzie Avenue
Happy Hour, Dinner: Bartholomew's, 777 Douglas Street (entrance on Humboldt Street)
Organizers
- Nancy Ann Neudauer, Pacific University, nancy (at) pacificu (dot) edu, Program Chair
- Amites Sarkar, Western Washington University, amites (dot) sarkar (at) wwu (dot) edu, Communications Chair
- Gary MacGillivray, University of Victoria, gmacgill (a) math (dot) uvic (dot) ca, Local Arrangements Chair