Тетрадка.бгГрафи на Рамзи.

През 1953г. е зададена на ученически конкурс, а по късно побликувана в американското списание Amer. Math Monthly, задачата: Какъв е максималният брой хора в компания, в която няма нито тройки познати, нито тройки непознати? Търсеният брой е 5. Следователно във всяка компания от 6 души има поне една тройка познати или непознати. Още нещо, във всяка такава компания има поне две тройки от познати или непознати(без да се изисква и двете тройки да са познати или непознати – може едната да е от познати, а другата от непознати). Съществуват 6 членни компании съставени от само 2 тройки познати или непознати. Ако разгледаме задачата за 6-членната компания в теорията на графите тя изглежда така: ако всяко от ребрата на пълния граф с шест върха оцветим в един от два предварително дадени цвята, ще получим поне един едноцветен триъгълник. Ако един граф, подобно на пълния граф с 6 върха, има свойството при произволно оцветяване в два цвята, да се получава едноцветен триъгълник, страните на който са ребра на графа, тогава този граф се нарича граф на Рамзи. През 1930г., английският математик Ф.П. Рамзи доказва, че за произволно естествено p може да се намери такова естествено числ