## 1 Introduction  
Motivated by the observation that most companies are more likely to consider job applicants suggested by their employees than those who apply on their own, [PERSON] and [PERSON] [1] modeled a job market that integrates social networks into stable matchings. Formally, an instance of their model consists of a set of firms \(F\), a set of workers \(W\), and a social network graph \(G\) of the workers. Each member of \(F\cup W\) has a preference list that ranks members of the opposite group that it or she finds acceptable in some linear order. Each firm \(f\) has a capacity \(q_{f}\), the maximum number of workers it can employ. A firm-worker pair is _acceptable_ if they appear in each other's preference lists. A (many-to-one) _matching_\(\mu\) of \(F\) and \(W\) is a set of acceptable firm-worker pairs where each firm \(f\) is part of at most \(q_{f}\) pairs and each worker is part of at most one pair. It has a _blocking pair_\((f,w)\) if (i) \((f,w)\) is an acceptable pair; (ii)\(f\) has an opening or \(f\) prefers \(w\) to its worst employee under \(\mu\); and (iii) \(w\) is unemployed or \(w\) prefers \(f\) to her employer under \(\mu\). This blocking pair is _local_ if additionally \(f\) and \(w\) have access to each other--_i.e._, \(f\) has an employee that is also a neighbor of \(w\) in \(G\). In two-sided matching theory, a common goal is to find _stable matchings_, which are matchings with no blocking pairs. In this model, the matchings of interest are _locally stable matchings_, which are matchings with no local blocking pairs. We emphasize that a locally stable matching can contain blocking pairs, but these blocking pairs are unlikely to compromise the matching. This may seem odd--if \(f\) still has an opening or prefers \(w\) over its worst employee, why \(f\) cannot just make a job offer to \(w\)? If \(w\) is unemployed or prefers \(f\) over her current employer, why she cannot just apply to \(f\)? In the job market context, we can think of the preference lists of \(f\) and \(w\) as being constructed in an online fashion. In particular, \(w\) can be included in \(f\)'s list only _after_\(f\) has seen \(w\)'s resume. However, for \(f\) to consider \(w\), some employee of \(f\) who is also a friend of \(w\) must forward \(w\)'s resume to \(f\). Similarly, \(f\) can be included in \(w\)'s list only _after_\(w\) has gained some reliable information about \(f\). For this to happen, \(w\) must have a friend who works at \(f\). This friend of \(w\) that is also an employee of \(f\) is a _point of contact_ between \(f\) and \(w\). The main assumption in this model is that a blocking pair of a matching cannot affect the matching if the firm-worker pair has no points of contact. Note, however, that although a firm-worker pair \((f,w)\) may exist such that \(w\) has no social ties with any of \(f\)'s other acceptable partners, \((f,w)\) can still be involved in a matching. The first part of [PERSON] and [PERSON]'s paper [1] explores the combinatorial differences between stable matchings and locally stable matchings. Among others, they show that there are instances whose set of locally stable matchings do not form a distributive lattice under the standard ordering relation used for stable matchings. There are also instances whose locally stable matchings vastly outnumber its stable matchings. The second part of their paper examines the evolution of the job market. They consider a decentralized version of [PERSON] and [PERSON]'s algorithm and show that for a specific case the algorithm converges to a locally stable matching under weak stochastic conditions. They then go on to analyze the goodness of the resulting locally stable matching. The recent work of [PERSON] [2] expands on the latter line of inquiry significantly. **Our Contribution. ** In this paper, we continue the study of locally stable matchings, focusing on those with maximum cardinality. We call them the _maximum locally stable matchings_.