{"id":1070,"date":"2014-10-20T00:01:11","date_gmt":"2014-10-20T04:01:11","guid":{"rendered":"http:\/\/matroidunion.org\/?p=1070"},"modified":"2014-10-20T15:58:39","modified_gmt":"2014-10-20T19:58:39","slug":"sudoku-matroids-and-graph-colouring-verification","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=1070","title":{"rendered":"Sudoku Matroids and Graph Colouring Verification"},"content":{"rendered":"

As this is my first post, I feel obliged to say the obligatory Hello World!<\/em>. With that aside, the problem I am going to discuss comes from the popular game Sudoku<\/em>. Suppose that we are given a filled Sudoku $S$ (which we cannot see), and we wish to verify its correctness. To do so, we are granted access to an oracle which can tell us if $S$ is consistent on any row, column or block. \u00a0Consistent<\/em> simply means that each number from 1 to 9 appears exactly once.<\/p>\n

Question 1. \u00a0<\/strong>How many checks are necessary to verify that $S$ is correct?<\/em><\/p>\n

Certainly, 27 checks is sufficient, but can we do better? Here’s a short proof that we can in fact do better.<\/p>\n

Proposition 2. \u00a0<\/strong>Every Sudoku can be verified with at most 21 checks.<\/em><\/p>\n

Proof. \u00a0<\/em>It will be convenient to fix some notation. Let<\/p>\n

$$K:= \\{r_1, \\dots, r_9\\} \\cup \\{c_1, \\dots, c_9\\} \\cup \\{b_1, \\dots, b_9\\}$$<\/p>\n

be the set of rows, columns and blocks of a Sudoku. By convention, the blocks are labelled as you (an English reader) would read the words along a page. Now suppose that a Sudoku $S$ is consistent\u00a0on $b_1, b_2, b_3, r_1$ and $r_2$. We claim that this implies $S$ is also consistent on $r_3$.<\/p>\n

Suppose not. Then some number, say 1, appears at least twice in $r_3$. However, since $S$ is consistent on $r_1$ and $r_2$, 1 appears exactly once in each of $r_1$ and $r_2$. Thus, 1 appears at least 4 times in $b_1 \\cup b_2 \\cup b_3$. \u00a0By the Pigeonhole Principle, 1 appears at least twice in $b_1, b_2$ or $b_3$, which is a contradiction. Thus, to verify $S$ it suffices to check $K \\setminus (\\{r_3, r_6, r_9\\} \\cup \\{c_3, c_6, c_9\\})$. $\\square$<\/p>\n

Can we do better than 21 checks? At first this seems rather tricky. \u00a0One can use information theory considerations to prove lower bounds. \u00a0For example, clearly at least 9 checks are necessary, since otherwise there will be a cell $x$ for which the row, column and box containing $x$ are all unchecked. \u00a0However, it seems difficult to get to a lower bound of 21 in this way. See this MathOverflow question<\/a> for someone trying to carry this out.<\/p>\n

At this point though, our hero Matroid Theory comes to the rescue. That is, somewhat remarkably, there is a matroid structure underlying this problem, which I will now describe. Define a subset\u00a0$V$ of $K$ to be a verifier<\/em> if every Sudoku which is consistent on $V$ is consistent everywhere.<\/p>\n

Theorem 3. \u00a0<\/strong>The set of minimal (under inclusion) verifiers $\\mathcal{V}$ is the set of bases of a matroid on $K$.<\/em><\/p>\n

There is a nice proof of this fact by Emil Je\u0159\u00e1bek as an answer to the same MathOverflow question<\/a> above. \u00a0It turns out that this matroid is actually representable (over $\\mathbb{Q}$) and\u00a0that the proof is also valid for the more general $n \\times n$ versions of Sudoku. We will not say anything more about the proof due to space limitations. \u00a0However, using the fact that $M=(K, \\mathcal{V})$ is a matroid, it is now easy to show that 21 is in fact the answer to Question 1.<\/p>\n

Proposition 4.<\/strong> \u00a0The minimum number of checks needed to verify the correctness of a Sudoku is 21.<\/em><\/p>\n

Proof.<\/em> \u00a0Translated into matroid theory language, the original question is simply asking what the rank of $M$ is. We have already shown that\u00a0$B:=K \\setminus (\\{r_3, r_6, r_9\\} \\cup \\{c_3, c_6, c_9\\})$ is a verifier, so it suffices to show that it is a minimal verifier. Certainly, we cannot\u00a0remove a block from $B$ and remain verifying, since there would then be a completely unchecked cell. On the other hand, for any two rows (or columns) $a$ and $b$\u00a0in the same band, it is easy to construct a Sudoku which is consistent everywhere except $a$ and $b$. Thus, we also cannot remove a row or column from $B$ and remain\u00a0verifying. $\\square$<\/p>\n

Of course, there is nothing special about the Sudoku graph, and we can attempt to play this game on an arbitrary graph. Let $G$ be a graph and\u00a0suppose that we wish to verify the correctness of a (not necessarily proper) $\\chi(G)$-colouring $C$ of $G$. Again we are given\u00a0access to an oracle which can tell us whether $C$ is consistent on any maximal clique of $G$. As before, we can define the set family $(K(G), \\mathcal{V}(G))$, where $K(G)$ is the set of maximal cliques of $G$ and $\\mathcal{V}(G)$ is the family of minimal verifiers.<\/p>\n

We now arrive at our main problem.<\/p>\n

Problem 5. \u00a0<\/strong>Characterize the graphs $G$ for which $(K(G), \\mathcal{V}(G))$ is a matroid.<\/em><\/p>\n

We now show that there are many such graphs.<\/p>\n

Proposition 6. \u00a0<\/strong>For all bipartite graphs $G$, $(K(G), \\mathcal{V}(G))$ is a matroid.<\/em><\/p>\n

Proof.<\/em> \u00a0We may assume that $G$ is connected. Since $G$ is bipartite, its set of maximal cliques is simply its set of edges. Let $T \\subseteq E(G)$ be\u00a0a minimal verifier. Evidently, $T$ must span all the vertices of $G$. On the other hand, if a 2-colouring of $G$ is correct on a spanning tree, then it is correct\u00a0everywhere. Thus, $T$ is a spanning tree, and so $(K(G), \\mathcal{V}(G))$ is actually the graphic matroid of $G$. $\\square$<\/p>\n

It would be nice if there were a unified proof that worked for both the bipartite case and the Sudoku graphs. Such a proof would have to utilize\u00a0some common structure of these two classes, since it is not true that for all graphs $G$, $(K(G), \\mathcal{V}(G))$ is a matroid.<\/p>\n

Proposition 7. \u00a0<\/strong>If $G=K_{2,2,2}$, then $(K(G), \\mathcal{V}(G))$ is not a matroid.<\/em><\/p>\n

Proof.<\/em> \u00a0It will be convenient to regard $K_{2,2,2}$ as the octahedron $O$. Let $1234$ be the middle 4-cycle of $O$ and $t$ and $b$ be the top and bottom vertices. \u00a0Now, it is easy to see that $B_1:=\\{t12, t34, b23\\}$ and $B_2:=\\{t23, t14, b34\\}$ are minimal verifiers. On the other hand, one easily checks that basis exchange fails for $B_1$ and\u00a0$B_2$. $\\square$<\/p>\n

There are also many interesting questions that one can ask about the framework we have set up for graph colouring verification. \u00a0For example, we can define the verification number<\/em> of a graph $G$ to be the minimum size of a verifier\u00a0(this is the the same thing as the size of a minimal verifier if $(K(G), \\mathcal{V}(G))$ is a matroid).<\/p>\n

Question 8.<\/strong> \u00a0Among all $n$-vertex graphs, which ones have the largest verification number?<\/em><\/p>\n

I was not able to find much in the literature, so any comments or references would be appreciated. Thanks for reading and see you in $3 + \\epsilon$ months!<\/p>\n

Acknowledgements.<\/strong> \u00a0Parts of this post are based on contributions from Fran\u00e7ois Brunault, Emil Je\u0159\u00e1bek and Zack Wolske on MathOverflow\u00a0and from Ross Kang, Rohan Kapadia, Peter Nelson and Irene Pivotto at Winberie’s in Princeton.<\/p>\n","protected":false},"excerpt":{"rendered":"

As this is my first post, I feel obliged to say the obligatory Hello World!. With that aside, the problem I am going to discuss comes from the popular game Sudoku. Suppose that we are given a filled Sudoku $S$ … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":10,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1070","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1070","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/10"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1070"}],"version-history":[{"count":10,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1070\/revisions"}],"predecessor-version":[{"id":1080,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1070\/revisions\/1080"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1070"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1070"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1070"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}