Fetching the paper…
Reading the bibliography…
We show, for any positive integer k, that there exists a graph in which any equitable partition of its vertices into k parts has at least ck^2/\log^* k pairs of parts which are not \epsilon-regular, where c,\epsilon>0 are absolute constants.
K. F. Roth, On certain sets of integers, J. London Math. Soc
1953
Earlier work this paper cites.
W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc
1963
Earlier work this paper cites.
E. Szemerédi, On graphs containing no complete subgraph with 4 vertices, Mat. Lapok
1972
Earlier work this paper cites.
M. Ajtai and E. Szemerédi, Sets of lattice points that form no squares, Stud. Sci. Math. Hungar
1974
Earlier work this paper cites.
E. Szemerédi, Integer sets containing no k k elements in arithmetic progression, Acta Arith
1975
Earlier work this paper cites.
I. Z. Ruzsa and E. Szemerédi, Triple systems with no six points carrying three triangles, in Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18, Volume II, 939–945
1976
Earlier work this paper cites.
E. Szemerédi, Regular partitions of graphs, in Colloques Internationaux CNRS 260 - Problèmes Combinatoires et Théorie des Graphes, Orsay (1976), 399–401
1976
Earlier work this paper cites.
R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey theory
1980
Earlier work this paper cites.
P. Erdős, P. Frankl, and V. Rödl, The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs Combin
1986
Earlier work this paper cites.
A. G. Thomason, Pseudorandom graphs, in Random graphs ’85 (Poznań, 1985), North-Holland Math. Stud. Vol. 144, North-Holland, Amsterdam, 1987, 307–331
1987
Earlier work this paper cites.
F. R. K. Chung, R. L. Graham, R. M. Wilson, Quasi-random graphs, Combinatorica
1989
Earlier work this paper cites.
N. Alon, R. A. Duke, H. Lefmann, V. Rödl, and R. Yuster, The algorithmic aspects of the regularity lemma, J. Algorithms
1994
Earlier work this paper cites.
R. A. Duke, H. Lefmann, and V. Rödl, A fast approximation algorithm for computing the frequencies of subgraphs in a given graph. SIAM J. Comput
1995
Earlier work this paper cites.
A. Frieze and R. Kannan, The regularity lemma and approximation schemes for dense problems, Proceedings of the 37th IEEE FOCS
1996
Earlier work this paper cites.
J. Komlós and M. Simonovits, Szemerédi’s regularity lemma and its applications in graph theory, in Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc. Math. Stud. 2, János Bolyai Math. Soc., Budapest, 1996, 295–352
1996
Cited alongside, same era.
R. Rubinfield and M. Sudan, Robust characterization of polynomials with applications to program testing, SIAM J. Comput
1996
Cited alongside, same era.
W. T. Gowers, Lower bounds of tower type for Szemerédi’s uniformity lemma, Geom. Funct. Anal
1997
Cited alongside, same era.
P. E. Haxell, Partitioning complete bipartite graphs by monochromatic cycles, J. Combin. Theory Ser. B
1997
Cited alongside, same era.
B. Bollobás, The work of William Timothy Gowers, Proceedings of the International Congress of Mathematicians, Vol. I (Berlin, 1998). Doc. Math
1998
Cited alongside, same era.
J. Solymosi, Note on a generalization of Roth’s theorem, in Discrete and computational geometry, Algorithms Combin. Vol. 25, Ed. János Pach, Springer, 2003, 825–827
2003
Later among the works it cites.
N. Alon and A. Shapira, Testing Subgraphs in Directed Graphs, J. Comput. System Sci
2004
Later among the works it cites.
N. Alon and A. Shapira, A characterization of easily testable induced subgraphs. Combin. Probab. Comput
2006
Later among the works it cites.
M. Krivelevich and B. Sudakov, Pseudo-random graphs, in More sets, graphs and numbers, Bolyai Soc. Math. Stud. 15, Springer, Berlin, 2006, 199–262
2006
Later among the works it cites.
T. Tao, Szemerédi’s regularity lemma revisited, Contrib. Discrete Math
2006
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
N. Eaton, Ramsey numbers for sparse graphs, Discrete Math
1998
Cited alongside, same era.
O. Goldreich, S. Goldwasser, and D. Ron, Property testing and its applications to learning and approximation, J. ACM
1998
Cited alongside, same era.
A. Frieze and R. Kannan, Quick approximation to matrices and applications, Combinatorica
1999
Cited alongside, same era.
N. Alon, E. Fischer, M. Krivelevich, and M. Szegedy, Efficient testing of large graphs, Combinatorica
2000
Cited alongside, same era.
N. Alon, Testing subgraphs in large graphs, Random Structures Algorithms
2002
Cited alongside, same era.
Y. Peng, V. Rödl, and A. Ruciński, Holes in graphs, Electron. J. Combin
2002
Cited alongside, same era.
N. Alon, W. Fernandez de la Vega, R. Kannan, and M. Karpinski, Random sampling and approximation of MAX-CSPs, J. Comput. System Sci
2003
Cited alongside, same era.
N. Alon, E. Fischer, and I. Newman, Efficient testing of bipartite graphs for forbidden induced subgraphs, SIAM J. Comput
2007
Later among the works it cites.
L. Lovász and B. Szegedy, Szemerédi’s lemma for the analyst, Geom. Funct. Anal
2007
Later among the works it cites.
V. Rödl and M. Schacht, Regular partitions of hypergraphs: regularity lemmas, Combin. Probab. Comput
2007
Later among the works it cites.
N. Alon, A. Shapira, and U. Stav, Can a graph have distinct regular partitions? SIAM J. Discrete Math
2008
Later among the works it cites.
N. Alon and J. H. Spencer, The probabilistic method
2008
Later among the works it cites.
N. Bansal and R. Williams, Regularity lemmas and combinatorial algorithms, Proceedings of the 50th IEEE FOCS
2009
Later among the works it cites.
V. Rödl and M. Schacht, Regularity lemmas for graphs, in Fete of Combinatorics and Computer Science, Bolyai Soc. Math. Stud. 20, 2010, 287–325
2010
Later among the works it cites.
J. Fox, A new proof of the graph removal lemma, Ann. of Math
2011
Closest in time.