diff --git a/src/dependent.c b/src/dependent.c
index a64dae9..5953d16 100644
--- a/src/dependent.c
+++ b/src/dependent.c
@@ -283,6 +283,22 @@ static const GnmDependentClass managed_dep_class = {
 	managed_dep_debug_name,
 };
 
+static GSList *style_dep_changed (GnmDependent *dep);
+static GnmCellPos const *style_dep_pos (GnmDependent const *dep);
+static void style_dep_debug_name (GnmDependent const *dep, GString *target);
+static const GnmDependentClass style_dep_class = {
+	dummy_dep_eval,
+	NULL,
+	style_dep_changed,
+	style_dep_pos,
+	style_dep_debug_name,
+};
+typedef struct {
+	GnmDependent base;
+	GnmCellPos pos;
+} GnmStyleDependent;
+
+
 static GPtrArray *dep_classes = NULL;
 
 void
@@ -297,6 +313,7 @@ dependent_types_init (void)
 	g_ptr_array_add	(dep_classes, (gpointer)&dynamic_dep_class);
 	g_ptr_array_add	(dep_classes, (gpointer)&name_dep_class);
 	g_ptr_array_add	(dep_classes, (gpointer)&managed_dep_class);
+	g_ptr_array_add	(dep_classes, (gpointer)&style_dep_class);
 
 #if USE_POOLS
 	micro_few_pool =
@@ -1152,6 +1169,39 @@ workbook_unlink_3d_dep (GnmDependent *dep)
 	g_hash_table_remove (wb->sheet_order_dependents, dep);
 }
 
+GSList *
+gnm_dep_style_dependency (Sheet *sheet,
+			  GnmExprTop const *texpr,
+			  GnmRange const *r)
+{
+	int row, col;
+	GSList *res = NULL;
+
+	/*
+	 * FIXME: Maybe do better for an expression that is just an
+	 * absolute ref.
+	 */
+
+	for (row = r->start.row; row <= r->end.row; row++) {
+		for (col = r->start.col; col <= r->end.col; col++) {
+			GnmStyleDependent *sd = g_new0 (GnmStyleDependent, 1);
+			GnmDependent *dep = &sd->base;
+
+			dep->sheet = sheet;
+			dep->flags = DEPENDENT_STYLE;
+			dep->texpr = NULL;
+			sd->pos.col = col;
+			sd->pos.row = row;
+
+			dependent_set_expr (dep, texpr);
+			dependent_link (dep);
+			res = g_slist_prepend (res, dep);
+		}
+	}
+
+	return res;
+}
+
 /*****************************************************************************/
 
 static void
@@ -1272,6 +1322,45 @@ managed_dep_debug_name (GnmDependent const *dep, GString *target)
 
 /*****************************************************************************/
 
+static GSList *
+style_dep_changed (GnmDependent *dep)
+{
+	GnmCellPos const *pos = dependent_pos (dep);
+	GnmCell *cell;
+	Sheet *sheet = dep->sheet;
+
+	g_printerr ("StyleDep %p at %s changed\n",
+		    dep, cellpos_as_string (pos));
+
+	/*
+	 * If the cell exists, unrender it so format changes can take
+	 * effect.
+	 */
+	cell = sheet_cell_get (sheet, pos->col, pos->row);
+	if (cell)
+		gnm_cell_unrender (cell);
+
+	sheet_redraw_region (sheet,
+			     pos->col, pos->row,
+			     pos->col, pos->row);
+
+	return NULL;
+}
+
+static GnmCellPos const *
+style_dep_pos (GnmDependent const *dep)
+{
+	return &((GnmStyleDependent*)dep)->pos;
+}
+
+static void
+style_dep_debug_name (GnmDependent const *dep, GString *target)
+{
+	g_string_append_printf (target, "StyleDep%p", (void *)dep);
+}
+
+/*****************************************************************************/
+
 static void
 name_dep_debug_name (GnmDependent const *dep, GString *target)
 {
diff --git a/src/dependent.h b/src/dependent.h
index aa150ff..82d2dbb 100644
--- a/src/dependent.h
+++ b/src/dependent.h
@@ -32,6 +32,7 @@ typedef enum {
 	DEPENDENT_DYNAMIC_DEP	   = 0x00000002,	/* builtin type */
 	DEPENDENT_NAME		   = 0x00000003,	/* builtin pseudo type */
 	DEPENDENT_MANAGED	   = 0x00000004,	/* builtin type */
+	DEPENDENT_STYLE		   = 0x00000005,	/* builtin type */
 	DEPENDENT_TYPE_MASK	   = 0x00000fff,
 
 	/* Linked into the workbook wide expression list */
@@ -110,6 +111,10 @@ void dependents_workbook_destroy  (Workbook *wb);
 void dependents_revive_sheet      (Sheet *sheet);
 void workbook_queue_all_recalc	  (Workbook *wb);
 
+GSList *gnm_dep_style_dependency (Sheet *sheet,
+				  GnmExprTop const *texpr,
+				  GnmRange const *r);
+
 GnmDepContainer *gnm_dep_container_new  (Sheet *sheet);
 void		 gnm_dep_container_dump	(GnmDepContainer const *deps,
 					 Sheet *sheet);
diff --git a/src/gnm-style-impl.h b/src/gnm-style-impl.h
index 1d3af77..7e58cb0 100644
--- a/src/gnm-style-impl.h
+++ b/src/gnm-style-impl.h
@@ -64,6 +64,8 @@ struct _GnmStyle {
 	GnmInputMsg		*input_msg;
 	GnmStyleConditions	*conditions;
 	GPtrArray		*cond_styles;
+
+	GSList *deps;
 };
 
 #define elem_changed(style, elem) do { (style)->changed |= (1u << (elem)); } while(0)
diff --git a/src/mstyle.c b/src/mstyle.c
index a134f9d..ab6df19 100644
--- a/src/mstyle.c
+++ b/src/mstyle.c
@@ -16,7 +16,10 @@
 #include "sheet-style.h"
 #include "style-conditions.h"
 #include "application.h"
+#include "parse-util.h"
+#include "expr.h"
 #include "gutils.h"
+#include "ranges.h"
 #include "gnumeric-conf.h"
 #include <goffice/goffice.h>
 
@@ -733,6 +736,9 @@ gnm_style_unref (GnmStyle const *style)
 		gnm_style_clear_pango (unconst);
 		gnm_style_clear_font (unconst);
 
+		if (style->deps)
+			g_warning ("Leftover style deps!");
+
 		CHUNK_FREE (gnm_style_pool, unconst);
 	}
 }
@@ -1748,6 +1754,89 @@ gnm_style_get_conditions (GnmStyle const *style)
 	return style->conditions;
 }
 
+void
+gnm_style_link_dependents (GnmStyle *style, GnmRange const *r)
+{
+	GnmStyleConditions *sc;
+	Sheet *sheet;
+	GSList *deps;
+
+	g_return_if_fail (style != NULL);
+	g_return_if_fail (r != NULL);
+
+	sheet = style->linked_sheet;
+	deps = style->deps;
+
+	/*
+	 * Conditional formatting.
+	 *
+	 * We need to trigger a reformatting of the cell if a cell referenced
+	 * by the condition changes.
+	 */
+	sc = elem_is_set (style, MSTYLE_CONDITIONS)
+		? gnm_style_get_conditions (style)
+		: NULL;
+	if (sc) {
+		GPtrArray const *conds = gnm_style_conditions_details (sc);
+		guint ui;
+		g_printerr ("Linking %s for %p\n", range_as_string (r), style);
+		for (ui = 0; ui < conds->len; ui++) {
+			GnmStyleCond const *c = g_ptr_array_index (conds, ui);
+			guint ei;
+
+			for (ei = 0; ei < 2; ei++) {
+				GnmExprTop const *texpr =
+					gnm_style_cond_get_expr (c, ei);
+				if (!texpr)
+					continue;
+				deps = g_slist_concat
+					(deps,
+					 gnm_dep_style_dependency
+					 (sheet, texpr, r));
+			}
+		}
+	}
+
+	/*
+	 * Validations.
+	 *
+	 * We can probably ignore those.  If a dependent cell changes such
+	 * that a validation condition is no longer satisfied, it is
+	 * grandfathers in a valid.
+	 */
+
+	/* The style owns the deps.  */
+	style->deps = deps;
+}
+
+void
+gnm_style_unlink_dependents (GnmStyle *style, GnmRange const *r)
+{
+	GSList *keep = NULL, *l, *next;
+
+	g_return_if_fail (style != NULL);
+	g_return_if_fail (r != NULL);
+
+	for (l = style->deps; l; l = next) {
+		GnmDependent *dep = l->data;
+		GnmCellPos const *pos = dependent_pos (dep);
+		next = l->next;
+
+		if (range_contains (r, pos->col, pos->row)) {
+			g_printerr ("Unlinking %s for %p\n", cellpos_as_string (pos), style);
+			dependent_set_expr (dep, NULL);
+			g_free (dep);
+			g_slist_free_1 (l);
+		} else {
+			l->next = keep;
+			keep = l;
+		}
+	}
+
+	style->deps = keep;
+}
+
+
 gboolean
 gnm_style_visible_in_blank (GnmStyle const *style)
 {
diff --git a/src/mstyle.h b/src/mstyle.h
index db1de9e..3a73eb2 100644
--- a/src/mstyle.h
+++ b/src/mstyle.h
@@ -158,6 +158,11 @@ GnmInputMsg	*gnm_style_get_input_msg	(GnmStyle const *style);
 void		 gnm_style_set_conditions	(GnmStyle *style, GnmStyleConditions *sc);
 GnmStyleConditions *gnm_style_get_conditions	(GnmStyle const *style);
 
+void             gnm_style_link_dependents      (GnmStyle *style,
+						 GnmRange const *r);
+void             gnm_style_unlink_dependents    (GnmStyle *style,
+						 GnmRange const *r);
+
 gboolean	 gnm_style_visible_in_blank (GnmStyle const *style);
 
 PangoAttrList	*gnm_style_generate_attrs_full (GnmStyle const *style);
diff --git a/src/ranges.c b/src/ranges.c
index 085fb78..50f8820 100644
--- a/src/ranges.c
+++ b/src/ranges.c
@@ -785,6 +785,14 @@ gnm_range_equal (const GnmRange *a, const GnmRange *b)
 	return range_equal (a, b);
 }
 
+guint
+gnm_range_hash (GnmRange const *r)
+{
+	return gnm_cellpos_hash (&r->start) * 10000019u +
+		gnm_cellpos_hash (&r->end);
+}
+
+
 GnmSheetRange *
 gnm_sheet_range_new (Sheet *sheet, GnmRange const *r)
 {
diff --git a/src/ranges.h b/src/ranges.h
index bb47e35..b7fefc4 100644
--- a/src/ranges.h
+++ b/src/ranges.h
@@ -22,8 +22,9 @@ G_BEGIN_DECLS
 			    (a)->end.col   == (b)->end.col)
 
 GType	  gnm_range_get_type (void); /* GBoxedType */
-GnmRange *gnm_range_dup	  (GnmRange const *r);
+GnmRange *gnm_range_dup (GnmRange const *r);
 gboolean  gnm_range_equal (GnmRange const *a, GnmRange const *b);
+guint     gnm_range_hash (GnmRange const *r);
 
 /**
  * range_overlap:
diff --git a/src/sheet-style.c b/src/sheet-style.c
index 43fc8b1..d9231c0 100644
--- a/src/sheet-style.c
+++ b/src/sheet-style.c
@@ -292,7 +292,7 @@ rstyle_dtor (ReplacementStyle *rs)
  * and will maintain the cache of styles associated with each sheet
  */
 static void
-rstyle_apply (GnmStyle **old, ReplacementStyle *rs)
+rstyle_apply (GnmStyle **old, ReplacementStyle *rs, GnmRange const *r)
 {
 	GnmStyle *s;
 	g_return_if_fail (old != NULL);
@@ -302,7 +302,7 @@ rstyle_apply (GnmStyle **old, ReplacementStyle *rs)
 		/* Cache the merged styles keeping a reference to the originals
 		 * just in case all instances change.
 		 */
-		s = (GnmStyle *)g_hash_table_lookup (rs->cache, *old);
+		s = g_hash_table_lookup (rs->cache, *old);
 		if (s == NULL) {
 			GnmStyle *tmp = gnm_style_new_merged (*old, rs->pstyle);
 			s = sheet_style_find (rs->sheet, tmp);
@@ -314,15 +314,28 @@ rstyle_apply (GnmStyle **old, ReplacementStyle *rs)
 
 	if (*old != s) {
 		if (*old) {
+			gnm_style_unlink_dependents (*old, r);
 			gnm_style_unlink (*old);
 		}
 
+		gnm_style_link_dependents (s, r);
 		gnm_style_link (s);
 
 		*old = s;
 	}
 }
 
+static GnmRange const *
+make_range (int col, int row, int w, int h)
+{
+	static GnmRange r;
+	r.start.col = col;
+	r.start.row = row;
+	r.end.col = col + (w - 1);
+	r.end.row = row + (h - 1);
+	return &r;
+}
+
 /****************************************************************************/
 
 /* If you change this, change the tile_{widths,heights} here
@@ -524,7 +537,8 @@ cell_tile_ptr_matrix_new (CellTile *t)
 }
 
 static CellTile *
-cell_tile_matrix_set (CellTile *t, GnmRange const *indic, ReplacementStyle *rs)
+cell_tile_matrix_set (CellTile *t, GnmRange const *indic, ReplacementStyle *rs,
+		      int cc, int cr, int level)
 {
 	int r, c;
 	CellTileStyleMatrix *res;
@@ -576,11 +590,14 @@ cell_tile_matrix_set (CellTile *t, GnmRange const *indic, ReplacementStyle *rs)
 
 	if (indic != NULL) {
 		GnmStyle **style = res->style;
-		r = indic->start.row;
-		style += r * TILE_SIZE_COL;
-		for ( ; r <= indic->end.row; ++r, style += TILE_SIZE_COL)
+		int const w = tile_widths[level];
+		int const h = tile_heights[level];
+		for (r = indic->start.row; r <= indic->end.row; ++r)
 			for (c = indic->start.col ; c <= indic->end.col ; ++c)
-				rstyle_apply (style + c, rs);
+				rstyle_apply (style + r * TILE_SIZE_COL + c, rs,
+					      make_range (cc + c * w,
+							  cr + r * h,
+							  w, h));
 	}
 
 	return (CellTile *)res;
@@ -726,7 +743,11 @@ sheet_style_resize (Sheet *sheet, int cols, int rows)
 static void
 cb_unlink (void *key, G_GNUC_UNUSED void *value, G_GNUC_UNUSED void *user)
 {
-	gnm_style_unlink (key);
+	GnmStyle *style = key;
+	GnmRange r;
+	range_init_full_sheet (&r, style->linked_sheet);
+	gnm_style_unlink_dependents (style, &r);
+	gnm_style_unlink (style);
 }
 
 #if USE_TILE_POOLS
@@ -742,10 +763,18 @@ void
 sheet_style_shutdown (Sheet *sheet)
 {
 	GnmStyleHash *table;
+	GnmRange r;
 
 	g_return_if_fail (IS_SHEET (sheet));
 	g_return_if_fail (sheet->style_data != NULL);
 
+	/*
+	 * Clear all styles.  This is an easy way to clear out all
+	 * style dependencies.
+	 */
+	range_init_full_sheet (&r, sheet);
+	sheet_style_set_range (sheet, &r, sheet_style_default (sheet));
+
 	cell_tile_dtor (sheet->style_data->styles);
 	sheet->style_data->styles = NULL;
 
@@ -879,19 +908,42 @@ sheet_style_update_grid_color (Sheet const *sheet)
 
 /****************************************************************************/
 
-static GnmStyle *
-vector_apply_pstyle (GnmStyle **styles, int n, ReplacementStyle *rs)
+static gboolean
+tile_is_uniform (CellTile const *tile)
 {
-	gboolean is_uniform = TRUE;
+	const int s = tile_size[tile->type];
+	GnmStyle const *st = tile->style_any.style[0];
 	int i;
 
-	for (i = 0; i < n; i++) {
-		rstyle_apply (styles + i, rs);
-		if (styles[i] != styles[0])
-			is_uniform = FALSE;
-	}
+	for (i = 1; i < s; i++)
+		if (tile->style_any.style[i] != st)
+			return FALSE;
+
+	return TRUE;
+}
+
+static void
+vector_apply_pstyle (CellTile *tile, ReplacementStyle *rs, int cc, int cr, int level)
+{
+	static const int xcounts[] = { 1, TILE_SIZE_COL, 1, TILE_SIZE_COL };
+	static const int ycounts[] = { 1, 1, TILE_SIZE_ROW, TILE_SIZE_ROW };
+	CellTileType type = tile->type;
+	const int s = tile_size[type];
+	const int xc = xcounts[type];
+	const int yc = ycounts[type];
+	int const w = tile_widths[level];
+	int const h = tile_heights[level];
+	int const w1 = tile_widths[level+1] / xc;
+	int const h1 = tile_heights[level+1] / yc;
+	int i;
 
-	return is_uniform ? styles[0] : NULL;
+	for (i = 0; i < s; i++) {
+		const GnmRange *r =
+			make_range (cc + w * (i % xc),
+				    cr + h * (i / xc),
+				    w1, h1);
+		rstyle_apply (tile->style_any.style + i, rs, r);
+	}
 }
 
 static gboolean
@@ -974,10 +1026,10 @@ cell_tile_apply (CellTile **tile, int level,
 	/* Apply new style over top of the entire tile */
 	if (full_width && full_height) {
 		if (TILE_SIMPLE <= type && type <= TILE_MATRIX) {
-			GnmStyle *uniform = vector_apply_pstyle (
-				(*tile)->style_any.style, tile_size[type], rs);
-			if (uniform && type != TILE_SIMPLE) {
-				res = cell_tile_style_new (uniform, TILE_SIMPLE);
+			vector_apply_pstyle (*tile, rs, corner_col, corner_row, level);
+			if (type != TILE_SIMPLE && tile_is_uniform (*tile)) {
+				res = cell_tile_style_new ((*tile)->style_any.style[0],
+							   TILE_SIMPLE);
 				cell_tile_dtor (*tile);
 				*tile = res;
 			}
@@ -997,13 +1049,19 @@ cell_tile_apply (CellTile **tile, int level,
 			if (type == TILE_COL) {
 				int i = indic.start.col;
 				for (;i <= indic.end.col ; ++i)
-					rstyle_apply ((*tile)->style_col.style + i, rs);
+					rstyle_apply ((*tile)->style_col.style + i,
+						      rs,
+						      make_range (corner_col + i * w,
+								  corner_row,
+								  w, height));
 				goto try_optimize;
 			}
 			if (type != TILE_PTR_MATRIX) {
 				indic.start.row = 0;
 				indic.end.row = TILE_SIZE_ROW - 1;
-				*tile = cell_tile_matrix_set (*tile, &indic, rs);
+				*tile = cell_tile_matrix_set (*tile, &indic, rs,
+							      corner_col, corner_row,
+							      level);
 				goto try_optimize;
 			}
 		}
@@ -1021,13 +1079,19 @@ cell_tile_apply (CellTile **tile, int level,
 			if (type == TILE_ROW) {
 				int i = indic.start.row;
 				for (;i <= indic.end.row ; ++i)
-					rstyle_apply ((*tile)->style_row.style + i, rs);
+					rstyle_apply ((*tile)->style_row.style + i,
+						      rs,
+						      make_range (corner_col,
+								  corner_row + i * h,
+								  width, h));
 				goto try_optimize;
 			}
 			if (type != TILE_PTR_MATRIX) {
 				indic.start.col = 0;
 				indic.end.col = TILE_SIZE_COL - 1;
-				*tile = cell_tile_matrix_set (*tile, &indic, rs);
+				*tile = cell_tile_matrix_set (*tile, &indic, rs,
+							      corner_col, corner_row,
+							      level);
 				goto try_optimize;
 			}
 		}
@@ -1037,7 +1101,9 @@ cell_tile_apply (CellTile **tile, int level,
 		    row_indicies (corner_row, h, apply_to,
 				  &indic.start.row, &indic.end.row) &&
 		    type != TILE_PTR_MATRIX) {
-			*tile = cell_tile_matrix_set (*tile, &indic, rs);
+			*tile = cell_tile_matrix_set (*tile, &indic, rs,
+						      corner_col, corner_row,
+						      level);
 			goto try_optimize;
 		}
 	}
@@ -1196,6 +1262,8 @@ cell_tile_apply_pos (CellTile **tile, int level,
 {
 	CellTile *tmp;
 	CellTileType type;
+	int col0 = col;
+	int row0 = row;
 
 	g_return_if_fail (col >= 0);
 	g_return_if_fail (col < gnm_sheet_get_max_cols (rs->sheet));
@@ -1233,10 +1301,12 @@ tail_recursion:
 		row -= r*h;
 		goto tail_recursion;
 	} else if (type != TILE_MATRIX)
-		*tile = tmp = cell_tile_matrix_set (tmp, NULL, NULL);
+		*tile = tmp = cell_tile_matrix_set (tmp, NULL, NULL, 0, 0, 0);
 
 	g_return_if_fail (tmp->type == TILE_MATRIX);
-	rstyle_apply (tmp->style_matrix.style + row*TILE_SIZE_COL + col, rs);
+	rstyle_apply (tmp->style_matrix.style + row * TILE_SIZE_COL + col,
+		      rs,
+		      make_range (col0, row0, 1, 1));
 }
 
 /**
@@ -3052,25 +3122,12 @@ cell_tile_optimize (CellTile **tile, int level, CellTileOptimize *data,
 
 	switch (type) {
 	case TILE_COL:
-	case TILE_ROW: {
-		int s = tile_size[type];
-		int i;
-		gboolean same = TRUE;
-
-		for (i = 1; i < s; i++) {
-			if (!gnm_style_eq ((*tile)->style_any.style[0],
-					   (*tile)->style_any.style[i])) {
-				same = FALSE;
-				break;
-			}
-		}
-
-		if (!same)
+	case TILE_ROW:
+		if (!tile_is_uniform (*tile))
 			return;
 
 		type = TILE_SIMPLE;
 		break;
-	}
 
 	case TILE_MATRIX: {
 		gboolean csame = TRUE;
