2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Клики в плотных подграфах
Сообщение26.12.2017, 22:33 
Граф $(V,E)$ назовём $\delta$-плотным если $|E| \ge \delta \binom{|V|}{2}$
Пусть дано целое $k$. Какую зависимость от $k$ имеет $\delta=\delta(k)$ минимальное из таких, что любой достаточно большой $\delta$-плотный граф содержит $k$-клику?

Например, $\delta(k)>\frac{1}{2}$, потому что всегда можно построить двудольный граф $K_{n/2,n/2}$, который будет $\frac{1}{2}$-плотным и не будет содержать нечётных циклов (а, значит, и клик). Но возможно ли построить сколь угодно большие более плотные графы без них?
Аналогично, $\delta(4) \ge \frac{2}{3}$, потому что есть трёхдольный граф $K_{n/3,n/3,n/3}$, где все возможные треугольники - только между долями, значит, клике размера 4 не бывать (она ж должна принадлежать какой-то доле).
Рассматривая точно так же полный $k$-дольный подграф, можно узнать, что $\delta(k) \ge \frac{k-1}{k}$.

А возможно ли улучшить эти оценки?

 
 
 
 Re: Клики в плотных подграфах
Сообщение27.12.2017, 07:30 
Прошу прощения, я опечатался несколько раз. Вместо "подграф" везде должно стоять просто "граф".

 
 
 
 Re: Клики в плотных подграфах
Сообщение30.12.2017, 09:48 
fractalon
Я не специалист, но знаю, что если граф содержит немного больше, чем $n^2/4$ ребер, то в нем всегда есть треугольник. Кажется, это называется теорема Турана. Факт очень хорошо известный. Т.е. $\delta(3)=1/2$. Вполне вероятно, что и для других $k$ тоже кое-что известно.

 
 
 
 Re: Клики в плотных подграфах
Сообщение30.12.2017, 12:10 
Аватара пользователя
vpb в сообщении #1280053 писал(а):
Вполне вероятно, что и для других $k$ тоже кое-что известно.
Да, это всё определяется той же теоремой Турана. На вопрос ТС отвечает граф Турана.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group