Резолюция является наиболее хорошо изученной системой доказательств. Известные техники для доказательств нижних оценок на данную систему плохо применимы в случае, когда формула <<перегружена>> переменными. Одним из ярких примеров <<нехорошей>> для резолюций формулы является Weak-PigeonHole (принцип Дирихле с m кроликами и n клетками, причем m >> n^2). Впервые нижняя оценка для данной формулы была доказана Разом в 2001 году, Разборов впоследствии усилил и обобщил с помощью своего так называемого метода псевдоширины.

На семинаре мы обсудим технику псевдо-ширины, и покажем нижнюю оценку на weak-PHP для разреженных графов. Совместная работа с Susanna F. de Rezende, Jakob Nordström и Kilian Risse.