Theory of graph homomorphisms and extremal combinatorics

点击翻译按钮获取中文摘要

Discrete mathematics or combinatorics is a fundamental mathematical discipline which focuses on the study of discrete objects and their properties. This area which is as old as the human ability to count, has attracted many strong mathematicians and is experiencing tremendous growth during the last fifty years. One of the main reasons for this is its intimate connection with computer science, the utility of which is obvious. Moreover combinatorics has applications to probability, set theory, cryptography, communication theory, the geometry of Banach spaces, harmonic analysis, number theory, ... the list goes on and on. However, still many of these applications would fail to impress many mathematicians who regard combinatorics as a large collection of isolated results and problems that can be disregarded as technical part of mathematics. This I believe is mainly due to the fact there has not been much theory developed to connect these results and problems to each other. However, in the last decade, this has started to change, and this change has gained more speed recently. A significant part of modern extremal combinatorics is dedicated to the study of the asymptotic relations between subgraph densities. These relations are usually expressed as algebraic inequalities between subgraph densities. Despite the variety of ingenious and hard results in asymptotic graph theory, surprisingly, there seem to exist only a handful of essentially different techniques in this area, and many known results are proven by clever combinations these techniques and tools. In recent years a new line of researches in the direction of developing theories that explains these similarities in the proofs of various seemingly very different results in this area has emerged. The purpose of this line of research is to develops a general theory that (1) reveals the general nature of this area of mathematics (2) encompasses the main techniques used in this area and provides methods for applying them in an automated manner (3) provides new tools for solving the large collection of open problems in this area. The problems that I am working on are the general problems that reveal the limitations and powers of these theories. These problems if solved will increase our general understanding of the nature of the area of extremal combinatorics. An important result in this area says that many theorems follow from the positive semi-definiteness of a certain infinite matrix. This positive semi-definite characterization is a powerful approach for proving such inequalities. This method is very convenient to program, so that the search for ``right'' relations can be to a large degree computerized. In other words, in this area certain type of problems which were previously solved by tedious work of important mathematics can now be solved by a computer problems. I have already used this method to solve an open problem, and in the future I am planning to combine this method with other auxiliary tools and techniques to attack to various open problems in extremal graph theory.