On graphs with subgraphs of large independence numbers
| dc.creator | Alon, Noga | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2007-06-27 | |
| dc.date.accessioned | 2026-07-07T08:12:49Z | |
| dc.date.available | 2026-07-07T08:12:49Z | |
| dc.description | Let G be a graph on n vertices in which every induced subgraph on s=\log^3 n vertices has an independent set of size at least t=\log n. What is the largest q=q(n) so that every such G must contain an independent set of size at least q ? This is one of several related questions raised by Erdos and Hajnal. We show that q(n)=Θ(\log^2 n/\log \log n), investigate the more general problem obtained by changing the parameters s and t, and discuss the connection to a related Ramsey-type problem. | |
| dc.identifier | https://arxiv.org/abs/0706.4099 | |
| dc.identifier | http://arxiv.org/abs/0706.4099 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/132587 | |
| dc.subject | Combinatorics | |
| dc.title | On graphs with subgraphs of large independence numbers | |
| dc.type | text |