JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 4, No 3 (1995)

Noga Alon

A graph G is t-tough if any induced subgraph of it with x > 1 connected components is obtained from G by deleting at least tx vertices. It is shown that for every t and g there are t-tough graphs of girth strictly greater than g. This strengthens a recent result of Bauer, van den Heuvel and Schmeichel who proved the above for g = 3, and hence disproves in a strong sense a conjecture of Chvátal that there exists an absolute constant t ₀ so that every t ₀-tough graph is pancyclic. The proof is by an explicit construction based on the tight relationship between the spectral properties of a regular graph and its expansion properties. A similar technique provides a simple construction of triangle-free graphs with independence number m on ( m ^4/3) vertices, improving previously known explicit constructions by Erdös and by Chung, Cleve and Dagum.

1. M. Ajtai, J. Koml6s, and E. Szemere'di, "A note on Ramsey numbers," J. Combinatorial Theory Ser. A 29 (1980), 354-360.
2. N. Alon, "Eigenvalues and expanders," Combinatorica 6 (1986), 83-96.
3. N. Alon and F.R.K. Chung, "Explicit construction of linear sized tolerant networks," Discrete Math. 72 (1988), 15-19; (Proc. of the First Japan Conference on Graph Theory and Applications, Hakone, Japan, 1986).
4. N. Alon, O. Goldreich, J. Hastad, and R. Peralta, "Simple constructions of almost k-wise independent random variables," Proc. 31st IEEE FOCS, St. Louis, Missouri, IEEE (1990), 544-553. See also: Random Structures and Algorithms 3 (1992), 289-304.
5. N. Alon and V.D. Milman, "A1, isoperimetric inequalities for graphs and superconcentrators," J. Comb. Theory, Ser. B 38 (1985), 73-88. See also: "Eigenvalues, expanders and superconcentrators," Proc. 25th IEEE FOCS, Singer Island, Florida, IEEE (1984), 320-322.
6. N. Alon and Y. Roichman, "Random Cayley graphs and expanders," Random Structures and Algorithms, 5 (1994), 271-284.
7. N. Alon and J.H. Spencer, The Probabilistic Method, Wiley, 1991.
8. D. Bauer, J. van den Heuvel and E. Schmeichel, Toughness and triangle-free graphs, (to appear).
9. B. Bollobds, Extremal Graph Theory, Academic Press, 1978.
10. V. Chvatal, "Tough graphs and Hamiltonian circuits," Discrete Mathematics 5 (1973), 215-218.
11. F.R.K. Chung, R. Cleve, and P. Dagum, "A note on constructive lower bounds for the Ramsey numbers R(3, t)," J. Combinatorial Theory Ser. B 57 (1993), 150-155.
12. R. Cleve and P. Dagum, "A constructive Q(t1.26) lower bound for the Ramsey number R(3, t)," Inter. Comp. Sci. Inst. Tech. Rep. TR-89-009, 1989.
13. H. Davenport, Multiplicative Number Theory, Springer Verlag, 1980 (Second Edition).
14. P. Erdos, "Graph Theory and Probability," Canad. J. Math. 11 (1959), 34-38.
15. P. Erdos, "Graph Theory and Probability, II," Canad. J. Math. 13 (1961), 346-352.
16. P. Erdos, "On the construction of certain graphs," J. Combinatorial Theory 1 (1966), 149-153.
17. L. Lovasz, Combinatorial Problems and Exercises, North Holland, Amsterdam, 1979, Problem 11.8.
18. A. Lubotzky, R. Phillips, and P. Sarnak, "Explicit expanders and the Ramanujan conjectures," Proc. 18th ACM STOC (1986), 240-246. See also: "Ramanujan graphs," Combinatorica 8 (1988), 261-277.
19. G.A. Margulis, "Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators," Problemy Peredachi Informatsii 24 (1988), 51-60 (in Russian). English translation in Problems of Information Transmission 24 (1988), 39-46.
20. F.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes, North Holland, Amsterdam, 1977.
21. J.B. Shearer, "A note on the independence number of a triangle-free graph," Discrete Math. 46(1983), 83-87.
22. J. Spencer, "Asymptotic lower bounds for Ramsey functions," Discrete Math. 20 (1977), 69-76.
23. R.M. Tanner, "Explicit construction of concentrators from generalized N-gons," SIAM J. Alg. Disc. Meth. 5 (1984), 287-293.