Extremal and Probabilistic Graph Theory

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

Denote by Hom(H, G) the set of all homomorphisms from a graph H to a graph G. A notorious and important conjecture of Erdos and Simonovits, now called the Sidorenko conjecture, is as follows. Given graphs G and H, with H bipartite, the probability that a uniform random mapping from V (H) to V (G) is a homomorphism is at least the product over all edges of the probability that the edge is mapped to an edge of G. A graph H is said to be a Sidorenko graph if this conjecture holds for all graphs G. In spite of determined attacks by many excellent mathematicians, the class of Sidorenko graphs is still rather small. Agnijo will try to enlarge this class considerably, or disprove the Erdos-Simonovits- Sidorenko conjecture. There are several other problems in extremal and probabilistic graph theory that Agnijo should try to solve.