Autotopism stabilized colouring games on rook's graphs

Autotopism stabilized colouring games on rook’s graphs Ra´ul M. Falc´on (University of Seville). (Joint work with S. Dominique Andres). (FernUniversit¨at in Hagen). Qwara. June 29, 2017. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs CONTENTS 1Colouring games and partial Latin rectangles. 2Compatibility and feasibility. 3The autotopism stabilized colouring game. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs I. Colouring games and partial Latin rectangles. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games. Steven J. Brams & Martin Gardner, 1981. Hans L. Boblaender, 1991. Based on the graph colouring problem, the game is played on a finite graph by two players, Alice (A) and Bob (B), with Alice playing first. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games. Steven J. Brams & Martin Gardner, 1981. Hans L. Boblaender, 1991. They alternately colour the vertices of the graph so that none two adjacent vertices are coloured with the same colour. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games. Steven J. Brams & Martin Gardner, 1981. Hans L. Boblaender, 1991. They alternately colour the vertices of the graph so that none two adjacent vertices are coloured with the same colour. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games. Steven J. Brams & Martin Gardner, 1981. Hans L. Boblaender, 1991. They alternately colour the vertices of the graph so that none two adjacent vertices are coloured with the same colour. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games. Steven J. Brams & Martin Gardner, 1981. Hans L. Boblaender, 1991. They alternately colour the vertices of the graph so that none two adjacent vertices are coloured with the same colour. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games. Steven J. Brams & Martin Gardner, 1981. Hans L. Boblaender, 1991. Alice wins if all vertices are coloured at the end of the game. Otherwise, Bob wins. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games on rook’s graphs. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games on rook’s graphs. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games on rook’s graphs. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games on rook’s graphs. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games on rook’s graphs. χgA= 3. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games on rook’s graphs. χgA= 3. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games on rook’s graphs. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games on rook’s graphs. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games on rook’s graphs. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Colouring games on rook’s graphs. χgB>3. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs II. Compatibility and feasibility. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Compatibility. A triple of positive integers (i,j,k) is lcm-compatible if lcm(i,j,k) = lcm(i,j) = lcm(i,k) = lcm(j,k). Proposition Θ=(α, β, γ)∈Ir,s,n.P∈ PLRΘ. (i,j,k)∈Ent(P)⇒(lα,i,lβ,j,lγ,k)is lcm-compatible. Θ = ((12),(1234),(1234)) ∈S3×S4×S4. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Compatibility. Θ=(α, β, γ)∈Ir,s,n. P∈ PLRr,s,nis Θ-compatible if, for each (i,j,k)∈Ent(P), C.1) (lα,i,lβ,j,lγ,k) is lcm-compatible. C.2) For each m≥0, Either the cell (αm(i), βm(j)) is empty or (αm(i), βm(j), γm(k)) ∈Ent(P). Θ = ((12),(1234),(1234)) ∈S3×S4×S4. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Compatibility. Θ=(α, β, γ)∈Ir,s,n. P∈ PLRr,s,nis Θ-compatible if, for each (i,j,k)∈Ent(P), C.1) (lα,i,lβ,j,lγ,k) is lcm-compatible. C.2) For each m≥0, Either the cell (αm(i), βm(j)) is empty or (αm(i), βm(j), γm(k)) ∈Ent(P). Theorem PLRΘ6=∅if and only if there exists a Θ-compatible P∈ PLRr,s,n for which every marked orbit is complete. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Feasibility. Θ=(α, β, γ)∈Ir,s,n. Feasible:λα iλβ jλγ k>0⇒(i,j,k) lcm-compatible. ((12)(34)(56),(123)(456),(123456)). Extension of size n0≥n: Any (α, β, γ0)∈Ir,s,n0, s. t. γ0(s) = γ(s),∀s≤n. Natural extension:γ0(s) = s,∀n<s. Extendable isotopism: All its natural extensions are feasible. Proposition Extendability ⇒Feasibility. If a natural extension of Θis feasible, then Θis feasible. Every feasible principal isotopism is extendable. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Feasibility. Θ=(α, β, γ)∈Ir,s,n. Feasible:λα iλβ jλγ k>0⇒(i,j,k) lcm-compatible. ((12)(34)(56),(123)(456),(123456)). Extension of size n0≥n: Any (α, β, γ0)∈Ir,s,n0, s. t. γ0(s) = γ(s),∀s≤n. Natural extension:γ0(s) = s,∀n<s. Extendable isotopism: All its natural extensions are feasible. Theorem (α, β, γ)is extendable if and only if it is feasible, and all the cycles of αand βhave the same length. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs III. The autotopism stabilized colouring game. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs The game. Initial board: Empty r×sarray: P= (pij ). Key: Θ = (α, β, γ)∈Ir,s,n. Basic rules: Alternately, the players colour an empty cell (i,j)∈[r]×[s] in the board with a colour c∈[n] by respecting the following rules: Rule 1) The Latin array condition must always hold. Rule 2) The Θ-compatibility condition must always hold. Rule 3) For each m<lcm(lα,i,lβ,j) and each coloured collinear cell (i0,j0) of (αm(i), βm(j)), it must be pi0j06=γm(c). Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs The game. Θ = ((12)(34),(12)(34),Id) Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs The game. Θ = ((12)(34),(12)(34),Id) Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs The game. If Θ = (Id,Id,Id), then χΘ g=χg. Lemma Let G= (V,E)be a graph with |E| 6=∅. Then, χgB(K2G)≤∆(K2G)) ≤∆(G)+1. Theorem χgA(R1,n) = χgB(R1,n) = n. χgA(R2,n) = n+ 1. χgB(R2,n) = n, for n≥2. χgA(R3,3) = 3. χgB(R3,3)=4. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs The game. Theorem χ((12)(34),(12)(34),Id) gA(R4,4)=5. χ((12)(34),(12)(34),Id) gB(R4,4)=4. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs References H. L. Bodlaender, On the complexity of some coloring games, Int. J. Found. Comput. Sci. 2(1991) 133–147. S. D. Andres and R. M. Falc´on, Colouring games based on autotopisms of Latin hyper-rectangles. Submitted. Preliminary version avalaible in arXiv:1707.00263 [math.CO]. R. M. Falc´on, Cycle structures of autotopisms of the Latin squares of order up to 11, Ars Comb. 103 (2012) 239–256. R. M. Falc´on, The set of autotopisms of partial Latin squares, Discrete Math. 313 (2013) 1150–1161. R. M. Falc´on and R. J. Stones, Classifying partial Latin rectangles, Electron. Notes Discrete Math. 49 (2015), 765–771. M. Gardner, Mathematical games, Scientific American (April, 1981), 23. M. Schlund, Graph decompositions, Latin squares, and games. Diploma Thesis, TU M¨unchen, 2011. D. S. Stones, P. Vojtˇechovsk´y and I. M. Wanless, Cycle structure of autotopisms of quasigroups and Latin squares, J. Combin. Des. 20 (2012) 227–263. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs Many thanks!! Autotopism stabilized colouring games on rook’s graphs Ra´ul M. Falc´on (University of Seville). (Joint work with S. Dominique Andres). (FernUniversit¨at in Hagen). Qwara. June 29, 2017. Ra´ul M. Falc´on and S. Dominique Andres Autotopism stabilized colouring games on rook’s graphs View publication statsView publication stats