报告题目：Fashion game, utilities of graphs and related problems
报告人：林文松，东南大学
报告时间：2024年5月19日（周日）10:00-11:00
报告地点：20-308
报告摘要：An instance of the fashion game is described as follows. There are two kinds of players in a graph G: Conformists and Rebels. All players choose their actions from an identical set of the two symmetric actions {0, 1}. An action profile π of G is a mapping from the vertex set of G to the action set {0, 1}. A conformist (resp. rebel) likes people having the same (resp. different) action with her and dislikes people having the different (resp. same) action. The utility u(v, π) of a player v under the action profile π is the number of neighbors she likes minus the number of neighbors she dislikes. The utility u(G, π) of G under π is the minimum utility among all players. Let t be an integer. A graph G is said to be t-satisfiable if there is an action profile of G such that all players have utilities at least t. The utility of G, denoted by u(G), is the maximum t such that G is t-satisfiable.
In this talk, we shall discuss some topics about fashion game and utilities of graphs, it involves some optimization problems, defective colorings and majority colorings.
This talk is based on joint works with Chenli Shen and Qi Wan
报告人简介：林文松，东南大学教授，博士生导师。1986至1993年就读于山东大学数学系运筹学专业，获理学学士学位和理学硕士学位。2001至2004年就读于香港浸会大学数学系，获博士学位。1993年至今在东南大学数学系任教。长期从事运筹学方面的教学和科研工作。先后主讲的本科生和研究生的课程有：图论及其应用、组合最优化、最优化理论与方法，离散数学、组合数学、运筹学、代数图论、随机图、现代图论等。主要研究方向：图论及其应用、网络最优化等。先后主持完成国家自然科学基金面上项目2项，江苏省自然科学基金面上项目1项，主持在研国家自然科学基金面上项目1项。已发表学术论文六十余篇。
邀请人：朱绪鼎