Grafs, amics i coneguts

Com és ben sabut, un graf és un objecte matemàtic que modelitza l'existència d'una certa relació entre parells d'elements d'un conjunt donat. Aleshores, és natural
que molts dels primers resultats sobre grafs facin referència a relacions entre persones
o grups de persones. En aquest article, comentem quatre resultats d'aquest tipus, els
quals tenen relació amb diverses teories generals de grafs i les seves aplicacions: el lema
de les encaixades de mans (relacionat amb la coloració de grafs i l'àlgebra booleana), un
lema sobre els coneguts i desconeguts en una festa (amb la teoria de Ramsey), un lema
sobre els amics en comú (amb la distància-regularitat i la teoria de codis) i el teorema
de les noces de Hall (amb la connectivitat de les xarxes). Aquestes quatre àrees de la
teoria de grafs, amb problemes sovint fàcils de plantejar però molt difícils de resoldre,
s'han desenvolupat extensament i actualment són motiu de nombrosos treballs de
recerca. Com a exemples de resultats i problemes representatius d'aquestes àrees,
els quals són motiu de discussió en aquest treball que presentem, podem citar els
següents: el teorema dels quatre colors (T4C), els nombres de Ramsey, els problemes
d'existència de grafs distància-regulars i de codis completament regulars i, finalment,
l'estudi de les propietats topològiques de les xarxes d'interconnexió.