%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/


%% Created for Larry Paulson at 2021-11-04 21:29:28 +0000 


%% Saved with string encoding Unicode (UTF-8) 



@book{diestel-graph,
	author = {Reinhard Diestel},
	booktitle = {Graph Theory},
	date-added = {2021-11-04 21:28:13 +0000},
	date-modified = {2021-11-04 21:29:19 +0000},
	publisher = {Springer},
	title = {Graph Theory},
	year = {2017}}

@techreport{szemeredi-regular,
	author = {Endre Szemer{\'e}di},
	date-added = {2021-11-04 20:50:28 +0000},
	date-modified = {2021-11-04 20:54:26 +0000},
	institution = {Stanford University Computer Science Department},
	month = apr,
	number = {STAN-CS-75-489},
	title = {Regular Partitions of Graphs},
	url = {http://i.stanford.edu/pub/cstr/reports/cs/tr/75/489/CS-TR-75-489.pdf},
	year = {1975},
	bdsk-url-1 = {http://i.stanford.edu/pub/cstr/reports/cs/tr/75/489/CS-TR-75-489.pdf}}

@article{malliaris-regularity,
	abstract = {We develop a framework in which Szemer{\'e}di's celebrated Regularity Lemma for graphs interacts with core model-theoretic ideas and techniques. Our work relies on a coincidence of ideas from model theory and graph theory: arbitrarily large half-graphs coincide with model-theoretic instability, so in their absence, structure theorems and technology from stability theory apply. In one direction, we address a problem from the classical Szemer{\'e}di theory. It was known that the "irregular pairs" in the statement of Szemer{\'e}di's Regularity Lemma cannot be eliminated, due to the counterexample of halfgraphs (i.e., the order property, corresponding to model-theoretic instability). We show that half-graphs are the only essential difficulty, by giving a much stronger version of Szemer{\'e}di's Regularity Lemma for models of stable theories of graphs (i.e. graphs with the non-k*-order property), in which there are no irregular pairs, the bounds are significantly improved, and each component satisfies an indivisibility condition. In the other direction, we take a more model-theoretic approach, and give several new Szemer{\'e}di-type partition theorems for models of stable theories of graphs. The first theorem gives a partition of any such graph into indiscernible components, meaning here that each component is either a complete or an empty graph, whose interaction is strongly uniform. This relies on a finitary version of the classic model-theoretic fact that stable theories admit large sets of indiscernibles, by showing that in models of stable theories of graphs one can extract much larger indiscernible sets than expected by Ramsey's theorem. The second and third theorems allow for a much smaller number of components at the cost of weakening the "indivisibility" condition on the components. We also discuss some extensions to graphs without the independence property. All graphs are finite and all partitions are equitable, i.e. the sizes of the components differ by at most 1. In the last three theorems, the number of components depends on the size of the graph; in the first theorem quoted, this number is a function of ε only as in the usual Szemer{\'e}di Regularity Lemma.},
	author = {M. Malliaris And S. Shelah},
	date-added = {2021-11-04 20:42:00 +0000},
	date-modified = {2021-11-04 20:42:00 +0000},
	issn = {00029947},
	journal = {Transactions of the American Mathematical Society},
	number = {3},
	pages = {1551-1585},
	publisher = {American Mathematical Society},
	title = {Regularity Lemmas for Stable Graphs},
	url = {http://www.jstor.org/stable/23813167},
	volume = {366},
	year = {2014},
	bdsk-url-1 = {http://www.jstor.org/stable/23813167}}
