Young domination on Hamming rectangles

Janko Gravner, Matjaž Krnc, Martin Milanič, Jean-Florent Raymond · 2025

Read Young domination on Hamming rectangles by Janko Gravner, Matjaž Krnc, Martin Milanič, Jean-Florent Raymond (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-03788.txt.

Introduction

Janko Gravner and co-authors frame a growth game on grids in a 2025 paper. The grids join two full webs as one board. A start set spreads by a rule drawn as a stair shape, and the ask is the least start that fills the board in a set count of rounds.

Their rule kin holds old topics at once: spread games, line growth, and far rule. For one-round fills they solve the least start in a run of plain cases. One case proves a guess left open since 2009. Pure math readers gain a shared tongue for a clan of spread asks.

Catalog record

CREATORJanko Gravner, Matjaž Krnc, Martin Milanič, Jean-Florent Raymond
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE96 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-03788

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Young domination on Hamming rectangles Janko Gravner, Matjaž Krnc, Martin Milanič, Jean-Florent Raymond Abstract We introduce a family of domination-type problems in Cartesian products of two graphs. The framework captures several well-studied topics, including variants of bootstrap percolation, line growth, distance domination, and target set selection. We focus on Cartesian products of two complete graphs and formulate the notion of Young domination number in terms of a growth rule determined by a Young diagram; this number is the smallest cardinality of an initial set that covers the entire vertex set in a prescribed number L L of iterations of the rule. We compute the Young domination number with L = 1 L=1 for several natural cases, including k k -domination for Cartesian products of two complete graphs of the same order, thereby proving a conjecture from 2009 due to Burchett, Lane, and Lachniet. We show that the case of L = 1 L=1 of Young domination is equivalent to computing bipartite Turán numbers for families of double stars, yielding implications of our results in extremal graph theory. For arbitrary fixed L L , we devise constant-factor approximation algorithms for the problem. Our approach is based on a variety of techniques, including duality between Young diagrams, algebraic formulations, explicit constructions, and dynamic programming. † † AMS 2000 subject classification : 05C35 (primary), 05C69, 05C85, 68W25. † † Key words and phrases : growth processes, bootstrap percolation, Young domination, k -domination, bipartite Turán numbers, Hamming graph, latency, spanning set. 1 Introduction 1.1 Motivation Looking for the smallest set of vertices in a graph with a given property is a natural and fundamental problem in extremal combinatorics and algorithmic graph theory. Variants of domination in graphs, in particular, have proved useful in many real-life contexts. We introduce Young domination , a family of domination-type problems in Cartesian products of graphs. This framework provides a common generalization of various well-studied problems, including bootstrap percolation [ GHPS ] , line growth [ GSS ] (also known as line percolation [ BBLN ] ), distance domination (see, e.g., [ Hen ] ), k -domination on rook’s graphs (see [ BLL ] , as well as [ HH , Section 8] ), and variants of target set selection with constant thresholds (see, e.g., [ CHLWY , LYW , JW ] ). Our problems are formulated in terms of a growth rule determined by a Young diagram, which ensures monotonicity; without this property, related questions become much less tractable (see, e.g., [ GG2 ] ). While we begin with a more general setup, we focus on growth dynamics on Cartesian products of two complete graphs, arguably the simplest nontrivial class. 1.2 Young domination We now proceed with formal definitions, starting with the growth rule parametrized by a Young diagram. The corresponding Young domination number will then be the smallest cardinality of an initial set that covers the entire vertex set in a prescribed number of iterations of the rule. Consider two finite graphs G_{1} and G_{2} . The Cartesian product of G_{1} and G_{2} is the graph G_{1}\Box G_{2} with vertex set V(G_{1})\times V(G_{2}) in which two vertices (u_{1},u_{2}) and (v_{1},v_{2}) are adjacent if and only if u_{1}=v_{1} and u_{2}v_{2}\in E(G_{2}) or u_{2}=v_{2} and u_{1}v_{1}\in E(G_{1}) . Each vertex v=(v_{1},v_{2})\in V(G_{1}\Box G_{2}) has neighbors divided into two disjoint sets: {\mathcal{N}}^{r}(v) , the row neighborhood of v , defined as the set of all vertices (v_{1},y) such that yv_{2} is an edge of G_{2} , and {\mathcal{N}}^{c}(v) , the column neighborhood of v , defined as the set of all vertices (x,v_{2}) such that xv_{1} is an edge of G_{1} . For an integer c\in{\mathbb{Z}}_{+}=\{0,1,2,\ldots\} , we denote by [0,c] the set \{0,1,\ldots,c\} . For integers a,b\geq 1 , we let R_{a,b}=[0,a-1]\times[0,b-1]\subseteq{\mathbb{Z}}_{+}^{2} be the discrete a\times b rectangle. A set {\mathcal{Z}}=\bigcup_{(a,b)\in I}R_{a,b} , given by a union of rectangles over some set I\subseteq\mathbb{N}^{2} , is called a (discrete) zero-set . We allow the trivial case {\mathcal{Z}}=\emptyset and also infinite {\mathcal{Z}} . Observe that zero-sets are exactly downward-closed sets in the sense that if (x,y)\in{\mathcal{Z}} and 0\leq x^{\prime}\leq x , 0\leq y^{\prime}\leq y then (x^{\prime},y^{\prime})\in{\mathcal{Z}} . Therefore, zero-sets are Young diagrams in the French notation [ Rom ] . Each zero-set determines a type of domination on Cartesian products of two graphs as follows. Given a zero-set {\mathcal{Z}} , the transformation \mathcal{T}=\mathcal{T}({\mathcal{Z}}) , defined on sets of vertices of G_{1}\Box G_{2} , assigns to every set A\subseteq V(G_{1}\Box G_{2}) a set \mathcal{T}(A)\subseteq V(G_{1}\Box G_{2}) as follows: • the input set is enlarged, i.e., if v\in A then v\in\mathcal{T}(A) ; • if v\in V(G_{1}\Box G_{2})\setminus A , then v\in\mathcal{T}(A) if and only if (|{\mathcal{N}}^{r}(v)\cap A|,|{\mathcal{N}}^{c}(v)\cap A|)\notin{\mathcal{Z}} . Thus, the iteration \mathcal{T}^{t}(A) yields a growth dynamics with initial set A=\mathcal{T}^{0}(A) , and we define \mathcal{T}^{\infty}(A)=\bigcup_{t\geq 0}\mathcal{T}^{t}(A) . Observe that \mathcal{T} is monotone : A_{1}\subseteq A_{2} implies \mathcal{T}(A_{1})\subseteq\mathcal{T}(A_{2}) ; in fact, \mathcal{T} is monotone if and only if its zero-set {\mathcal{Z}} is downward closed. We call the transformation \mathcal{T} , or equivalently, the resulting growth dynamics the neighborhood growth . For L=0,1,2,\ldots,\infty , we say that A is a {\mathcal{Z}} -dominating set with latency L if \mathcal{T}^{L}(A)=V(G_{1}\Box G_{2}) . Our focus is on smallest such sets, so we define the {\mathcal{Z}} -domination number of ({\mathcal{Z}},G_{1},G_{2}) with latency L as \gamma^{L}=\gamma^{L}({\mathcal{Z}},G_{1},G_{2})=\min\{|A|\colon\mathcal{T}^{L}(A)=V(G_{1}\Box G_{2})\}. It is trivially true that \gamma^{0}({\mathcal{Z}},G_{1},G_{2})=|V(G_{1}\Box G_{2})| . When the latency is not specified, we assume the default choice L=1 , often omit it from the notation and call \gamma=\gamma({\mathcal{Z}},G_{1},G_{2})=\gamma^{1}({\mathcal{Z}},G_{1},G_{2}) the {\mathcal{Z}} -domination number of ({\mathcal{Z}},G_{1},G_{2}) . In particular, if a\in\mathbb{N} and {\mathcal{Z}} is the triangle (1.1) T_{a}=\{(x,y)\in\mathbb{Z}_{+}^{2}\colon x+y\leq a-1\}, then \gamma(T_{a},G_{1},G_{2}) is exactly the a -domination number of the product graph G_{1}\Box G_{2} [ HV ] . Furthermore, \gamma^{L}(T_{1},G_{1},G_{2}) is exactly the distance- L domination number of the product graph G_{1}\Box G_{2} , for any finite L (see, e.g., [ Hen ] ). In our general discussions, or if {\mathcal{Z}} and L are clear from the context, we refer to {\mathcal{Z}} -domination with latency L as Young domination . Perhaps the most natural special case of Young domination is where the two factors are complete graphs, G_{1}=K_{m} and G_{2}=K_{n} on vertex sets [0,m-1] and [0,n-1] , in which case we write \gamma^{L}=\gamma^{L}({\mathcal{Z}},m,n)=\gamma^{L}({\mathcal{Z}},K_{m},K_{n})\,. The graph K_{m}\Box K_{n} is known as a Hamming rectangle , and neighborhood growth on this graph with general {\mathcal{Z}} was studied in [ GSS , GPS ] . As in these references, we represent this graph as having vertex set R_{n,m} ; see the beginning of Section 2 for more details. We focus solely on the neighborhood growth dynamics on Hamming rectangles for the remainder of the paper. See Figure 2.1 for an example. 1.3 Main results We begin with three special cases where Young domination number is given by simple expressions. The easiest are the L -shaped Young diagrams, given by zero-sets V_{a,b} , where a,b\geq 0 and (1.2) (V_{a,b})^{c}=\mathbb{Z}_{+}^{2}\setminus V_{a,b}=[a,\infty)\times[b,\infty), i.e., a point requires at least a occupied row neighbors and at least b occupied column neighbors to become occupied. Proposition 1.1 . Assume that {\mathcal{Z}}=V_{a,b} , where 0\leq a\leq n , 0\leq b\leq m . Then \gamma({\mathcal{Z}},m,n)=\max(am,bn) . Next we consider rectangular zero-sets R_{a,b} , whereby a point with at least a occupied row neighbors

Read the complete text