bluuebunny/crossref_metadata_2025_split huggingface dataset:
Beyond Sum-Free Sets in the Natural Numbers
Authors: Huczynska Sophie 
Published: January 2020

For an interval $[1,N] \subseteq \mathbb{N}$, sets $S \subseteq [1,N]$ with the property that $|\{(x,y) \in S^2:x+y \in S\}|=0$, known as sum-free sets, have attracted considerable attention. In this paper, we generalize this notion by considering $r(S)=|\{(x,y) \in S^2: x+y \in S\}|$, and analyze its behaviour as $S$ ranges over the subsets of $[1,N]$. We obtain a comprehensive description of the spectrum of attainable $r$-values, constructive existence results and structural characterizations for sets attaining extremal and near-extremal values.
A Bound on Permutation Codes
Authors: Bierbrauer Jürgen , Metsch Klaus 
Published: January 2020

Consider the symmetric group $S_n$ with the Hamming metric. A permutation code on $n$ symbols is a subset $C\subseteq S_n.$ If $C$ has minimum distance $\geq n-1,$ then $\vert C\vert\leq n^2-n.$ Equality can be reached if and only if a projective plane of order $n$ exists. Call $C$ embeddable if it is contained in a permutation code of minimum distance $n-1$ and cardinality $n^2-n.$ Let $\delta =\delta (C)=n^2-n-\vert C\vert$ be the deficiency of the permutation code $C\subseteq S_n$ of minimum distance $\geq n-1.$We prove that $C$ is embeddable if either $\delta\leq 2$ or if $(\delta^2-1)(\delta +1)^2<27(n+2)/16.$ The main part of the proof is an adaptation of the method used to obtain the famous Bruck completion theorem for mutually orthogonal latin squares.
Identifying Codes of Lexicographic Product of Graphs
Authors: Feng Min , Xu Min , Wang Kaishun 
Published: January 2020

Let $G$ be a connected graph and $H$ be an arbitrary graph. In this paper, we study the identifying codes of the lexicographic product $G[H]$ of $G$ and $H$. We first introduce two parameters of $H$, which are closely related to identifying codes of $H$. Then we provide the sufficient and necessary condition for $G[H]$ to be identifiable. Finally, if $G[H]$ is identifiable, we determine the minimum cardinality of identifying codes of $G[H]$ in terms of the order of $G$ and these two parameters of $H$.
Avoider-Forcer Games on Hypergraphs with Small Rank
Authors: Bednarska-Bzdęga Małgorzata 
Published: January 2020

We study biased $(a:f)$ Avoider-Forcer games played on hypergraphs, in the strict and monotone versions. We give a sufficient condition for Avoider's win, useful in the case of games on hypergraphs whose rank is smaller than $f$. We apply this result to estimate the threshold bias in Avoider-Forcer $(1:f)$ games in which Avoider is trying not to build a copy of a fixed graph $G$ in $K_n$. We also study the $d$-degree $(1:f)$ game in which Avoider's aim is to avoid a spanning subgraph of the minimal degree at least $d$ in $K_n$. We show that the strict 1-degree game has the threshold which is the same as the threshold of the Avoider-Forcer connectivity game.
On the Shannon Capacity of Triangular Graphs
Authors: Kizhakkepallathu Ashik Mathew , Östergård Patric RJ , Popa Alexandru 
Published: January 2020

The Shannon capacity of a graph $G$ is $c(G)=\sup_{d\geq 1}(\alpha(G^d))^{\frac{1}{d}},$ where $\alpha(G)$ is the independence number of $G$. The Shannon capacity of the Kneser graph $\mathrm{KG}_{n,r}$ was determined by Lovász in 1979, but little is known about the Shannon capacity of the complement of that graph when $r$ does not divide $n$. The complement of the Kneser graph, $\overline{\mathrm{KG}}_{n,2}$, is also called the triangular graph $T_n$. The graph $T_n$ has the $n$-cycle $C_n$ as an induced subgraph, whereby $c(T_n) \geq c(C_n)$, and these two families of graphs are closely related in the current context as both can be considered via geometric packings of the discrete $d$-dimensional torus of width $n$ using two types of $d$-dimensional cubes of width $2$. Bounds on $c(T_n)$ obtained in this work include $c(T_7) \geq \sqrt[3]{35} \approx 3.271$, $c(T_{13}) \geq \sqrt[3]{248} \approx 6.283$, $c(T_{15}) \geq \sqrt[4]{2802} \approx 7.276$, and $c(T_{21}) \geq \sqrt[4]{11441} \approx 10.342$.
The Size of Edge-critical Uniquely 3-Colorable Planar Graphs
Authors: Matsumoto Naoki 
Published: January 2020

A graph $G$ is uniquely $k$-colorable if the chromatic number of $G$ is $k$ and $G$ has only one $k$-coloring up to permutation of the colors. A uniquely $k$-colorable graph $G$ is edge-critical if $G-e$ is not a uniquely $k$-colorable graph for any edge $e\in E(G)$. In this paper, we prove that if $G$ is an edge-critical uniquely $3$-colorable planar graph, then $|E(G)|\leq \frac{8}{3}|V(G)|-\frac{17}{3}$. On the other hand, there exists an infinite family of edge-critical uniquely 3-colorable planar graphs with $n$ vertices and $\frac{9}{4}n-6$ edges. Our result gives a first non-trivial upper bound for $|E(G)|$.
Characterizations of Regularity for certain $Q$-Polynomial Association Schemes
Authors: Suda Sho 
Published: January 2020

It was shown that linked systems of symmetric designs with $a_1^*=0$ and mutually unbiased bases (MUBs) are triply regular association schemes. In this paper, we characterize triple regularity of linked systems of symmetric designs by its Krein number. And we prove that a maximal set of MUBs carries a quadruply regular association scheme and characterize the quadruple regularity of MUBs by its parameter.
Sparse Distance Sets in the Triangular Lattice
Authors: Ahmed Tanbir , Snevily Hunter 
Published: January 2020

A planar point-set $X$ in Euclidean plane is called a $k$-distance set if there are exactly $k$ different distances among the points in $X$. The function $g(k)$ denotes the maximum number of points in the Euclidean plane that is a $k$-distance set. In 1996, Erdős and Fishburn conjectured that for $k\geq 7$, every $g(k)$-point subset of the plane that determines $k$ different distances is similar to a subset of the triangular lattice. We believe that if $g(k)$ is an increasing function of $k$, then the conjecture is false. We present data that supports our claim and a method of construction that unifies known optimal point configurations for $k\geq 3$.
Vanishing of Doubly Symmetrized Tensors
Authors: Berget Andrew , Dias da Silva J. A. , Fonseca Amélia 
Published: January 2020

Symmetrizations of tensors by irreducible characters of the symmetric group serve as natural analogues of symmetric and skew-symmetric tensors. The question of when a symmetrized decomposable tensor is non-zero is intimately related to the rank partition of a matroid extracted from the tensor. In this paper we characterize the non-vanishing of the symmetrization of certain partially symmetrized decomposable tensors. Our answers are phrased in terms of rank partitions of matroids.
Random Walks on Quasirandom Graphs
Authors: Barber Ben , Long Eoin 
Published: January 2020

Let $G$ be a quasirandom graph on $n$ vertices, and let $W$ be a random walk on $G$ of length $\alpha n^2$. Must the set of edges traversed by $W$ form a quasirandom graph? This question was asked by Böttcher, Hladký, Piguet and Taraz. Our aim in this paper is to give a positive answer to this question. We also prove a similar result for random embeddings of trees.
Chains of Length 2 in Fillings of Layer Polyominoes
Authors: Phillipson Mitch , Yan Catherine H. , Yeh Jean 
Published: January 2020

The symmetry of the joint distribution of the numbers of crossings and nestings of length $2$ has been observed in many combinatorial structures, including permutations, matchings, set partitions, linked partitions, and certain families of graphs. These results have been unified in the larger context of enumeration of northeast and southeast chains of length $2$ in $01$-fillings of moon polyominoes. In this paper we extend this symmetry to fillings of a more general family—layer polyominoes, which are intersection-free and row-convex, but not necessarily column-convex. Our main result is that the joint distribution of the numbers of northeast and southeast chains of length $2$ over $01$-fillings is symmetric and invariant under an arbitrary permutation of rows.
Upper-Bounding the $k$-Colorability Threshold by Counting Covers
Authors: Coja-Oghlan Amin 
Published: January 2020

Let $G(n,m)$ be the random graph on $n$ vertices with $m$ edges. Let $d=2m/n$ be its average degree. We prove that $G(n,m)$ fails to be $k$-colorable with high probability if $d>2k\ln k-\ln k-1+o_k(1)$. This matches a conjecture put forward on the basis of sophisticated but non-rigorous statistical physics ideas (Krzakala, Pagnani, Weigt: Phys. Rev. E 70 (2004)). The proof is based on applying the first moment method to the number of "covers", a physics-inspired concept. By comparison, a standard first moment over the number of $k$-colorings shows that $G(n,m)$ is not $k$-colorable with high probability if $d>2k\ln k-k$.
On Divisibility of Convolutions of Central Binomial Coefficients
Authors: Sepanski Mark Roger 
Published: January 2020

Recently, Z. Sun proved that \[ 2(2m+1)\binom{2m}{m} \mid \binom{6m}{3m}\binom{3m}{m} \] for $m\in\mathbb{Z}_{>0}$. In this paper, we consider a generalization of this result by defining \[ b_{n,k}=\frac{2^{k}\, (n+2k-2)!!}{((n-2)!!\, k!}. \] In this notation, Sun's result may be expressed as $2\, (2m+1) \mid b_{(2m+1),(2m+1)-1}$ for $m\in\mathbb{Z}_{>0}$. In this paper, we prove that \[ 2n \mid b_{n,un\pm 2^{r}} \] for $n\in\mathbb{Z}_{>0}$ and $u,r\in\mathbb{Z}_{\geq 0}$ with $un \pm 2^{r} > 0$. In addition, we prove a type of converse. Namely, fix $k\in\mathbb{Z}$ and $u\in \mathbb{Z}_{≥0}$ with $u>0$ if $k<0$. If \[ 2n \mid b_{n,un+k} \] for all $n\in\mathbb{Z}_{>0}$ with $un+k>0$, then there exists a unique $r \in \mathbb{Z}_{≥0}$ so that either $k=2^{r} $ or $k=-2^{r}$.
On-Line Choice Number of Complete Multipartite Graphs: an Algorithmic Approach
Authors: Chang Fei-Huang , Chen Hong-Bin , Guo Jun-Yi , Huang Yu-Pei 
Published: January 2020

This paper studies the on-line choice number on complete multipartite graphs with independence number $m$. We give a unified strategy for every prescribed $m$. Our main result leads to several interesting consequences comparable to known results. (1) If $k_1-\sum_{p=2}^m\left(\frac{p^2}{2}-\frac{3p}{2}+1\right)k_p\geq 0$, where $k_p$ denotes the number of parts of cardinality $p$, then $G$ is on-line chromatic-choosable. (2) If $|V(G)|\leq\frac{m^2-m+2}{m^2-3m+4}\chi(G)$, then $G$ is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs $K_{m\star k}$ is at most$\left(m+\frac{1}{2}-\sqrt{2m-2}\right)k$ for $m\geq 3$.
About Half Permutations
Authors: Rinaldi Simone , Socci Samanta 
Published: January 2020

In 2011, Beaton et al. analytically proved that the number of directed column-convex permutominoes of size $n$ is given by $(n+1)!/2$. In this paper, we provide a different proof of this statement using a bijective method. More precisely, we present a bijective correspondence between the class $D_n$ of directed column-convex permutominoes of size $n$ and a set of permutations (called $dcc$-permutations) of length $n+1$, which we prove to be counted by $(n+1)!/2$. The class of $dcc$-permutations is a new class of permutations counted by half factorial numbers, and here we show some combinatorial characterizations of this class, using the concept of logical formulas determined by a permutation and the notion of mesh pattern.
Non-Existence of Point-transitive 2-(106, 6, 1) Designs
Authors: Guan Haiyan , Zhou Shenglin 
Published: January 2020

Let $\mathcal{S}$ be a linear space with 106 points, with lines of size 6, and let $G$ be an automorphism group of $\mathcal{S}$. We prove that $G$ cannot be point-transitive. In other words, there exists no point-transitive 2-(106, 6, 1) designs.
Signed Excedance Enumeration in the Hyperoctahedral group
Authors: Sivasubramanian Sivaramakrishnan 
Published: January 2020

Several signed excedance-like statistics have nice formulae or generating functions when summed over the symmetric group and over its subset of derangements. We give counterparts of some of these results when we sum over the hyperoctahedral group and its subset of derangements. Our results motivate us to define and derive attractive bivariate formulae which generalise some of these results for the symmetric group.
Minimum-Weight Edge Discriminators in Hypergraphs
Authors: Bhattacharya Bhaswar B. , Das Sayantan , Ganguly Shirshendu 
Published: January 2020

In this paper we introduce the notion of minimum-weight edge-discriminators in hypergraphs, and study their various properties. For a hypergraph $\mathcal H=(\mathcal V, \mathscr E)$, a function $\lambda: \mathcal V\rightarrow \mathbb Z^{+}\cup\{0\}$ is said to be an edge-discriminator on $\mathcal H$ if $\sum_{v\in E_i}{\lambda(v)}>0$, for all hyperedges $E_i\in \mathscr E$, and $\sum_{v\in E_i}{\lambda(v)}\ne \sum_{v\in E_j}{\lambda(v)}$, for every two distinct hyperedges $E_i, E_j \in \mathscr E$. An optimal edge-discriminator on $\mathcal H$, to be denoted by $\lambda_\mathcal H$, is an edge-discriminator on $\mathcal H$ satisfying $\sum_{v\in \mathcal V}\lambda_\mathcal H (v)=\min_\lambda\sum_{v\in \mathcal V}{\lambda(v)}$, where the minimum is taken over all edge-discriminators on $\mathcal H$. We prove that any hypergraph $\mathcal H=(\mathcal V, \mathscr E)$, with $|\mathscr E|=m$, satisfies $\sum_{v\in \mathcal V} \lambda_\mathcal H(v)\leq m(m+1)/2$, and the equality holds if and only if the elements of $\mathscr E$ are mutually disjoint. For $r$-uniform hypergraphs $\mathcal H=(\mathcal V, \mathscr E)$, it follows from earlier results on Sidon sequences that $\sum_{v\in \mathcal V}\lambda_{\mathcal H}(v)\leq |\mathcal V|^{r+1}+o(|\mathcal V|^{r+1})$, and the bound is attained up to a constant factor by the complete $r$-uniform hypergraph. Finally, we show that no optimal edge-discriminator on any hypergraph $\mathcal H=(\mathcal V, \mathscr E)$, with $|\mathscr E|=m~(\geq 3)$, satisfies $\sum_{v\in \mathcal V} \lambda_\mathcal H (v)=m(m+1)/2-1$. This shows that all integer values between $m$ and $m(m+1)/2$ cannot be the weight of an optimal edge-discriminator of a hypergraph, and this raises many other interesting combinatorial questions.
Structural Transition in Random Mappings
Authors: Hansen Jennie C. , Jaworski Jerzy 
Published: January 2020

In this paper we characterise the structural transition in random mappings with in-degree restrictions. Specifically, for integers $0~\!\!\leq~\!\!r\leq~\!\!n$, we consider a random mapping model $\hat{T}_n^r$ from $[n]=\{1,2, \ldots , n\}$ into $[n]$ such that $\hat{G}_n^r$, the directed graph on $n$ labelled vertices which represents the mapping $\hat{T}_n^r$, has $r$ vertices that are constrained to have in-degree at most $1$ and the remaining vertices have in-degree at most 2. When $r=n$, $\hat{T}_n^r$ is a uniform random permutation and when $r<n$, we can view $\hat{T}_n^r$ as a 'corrupted' permutation. We investigate structural transition in $\hat{G}_n^r$ as we vary the integer parameter $r$ relative to the total number of vertices $n$. We obtain exact and asymptotic distributions for the number of cyclic vertices, the number of components, and the size of the typical component in $\hat{G}_n^r$, and we characterise the dependence of the limiting distributions of these variables on the relationship between the parameters $n$ and $r$ as $n\to\infty$. We show that the number of cyclic vertices in $\hat{G}_n^r$ is $\Theta({n\over\sqrt{a}})$ and the number of components is $\Theta(\log({n\over \sqrt{a}}))$ where $a=n-r$. In contrast, provided only that $a=n-r\to\infty$, we show that the asymptotic distribution of the order statistics of the normalised component sizes of $\hat{G}_n^r$ is always the Poisson-Dirichlet(1/2) distribution as in the case of uniform random mappings with no in-degree restrictions.
Random Cyclations
Authors: Pippenger Nicholas 
Published: January 2020

Consider $n$ unit intervals, say $[1,2], [3,4], \ldots, [2n-1,2n]$. Identify their endpoints in pairs at random, with all $(2n-1)!! = (2n-1)(2n-3)\cdots 3\cdot 1$ pairings being equally likely. The result is a collection of cycles of various lengths, and we investigate the distribution of these lengths. The distribution is similar to that of the distribution of the lengths of cycles in a random permutation, but it also exhibits some striking differences.
On Computing the Degree of Convexity of Polyominoes
Authors: Brocchi Stefano , Castiglione Giuseppa , Massazza Paolo 
Published: January 2020

In this paper we present an algorithm which has as input a convex polyomino $P$ and computes its degree of convexity, defined as the smallest integer $k$ such that any two cells of $P$ can be joined by a monotone path inside $P$ with at most $k$ changes of direction. The algorithm uses space $O(m + n)$ to represent a polyomino $P$ with $n$ rows and $m$ columns, and has a running time $O(min(m; r k))$, where $r$ is the number of corners of $P$. Moreover, the algorithm leads naturally to a decomposition of $P$ into simpler polyominoes.
A Generalization of Aztec Diamond Theorem, Part I
Authors: Lai Tri 
Published: January 2020

We consider a new family of 4-vertex regions with zigzag boundary on the square lattice with diagonals drawn in. By proving that the number of tilings of the new regions is given by a power 2, we generalize both Aztec diamond theorem and Douglas' theorem. The proof extends an idea of Eu and Fu for Aztec diamonds, by using a bijection between domino tilings and non-intersecting Schröder paths, then applying Lindström-Gessel-Viennot methodology.
Split $(n+t)$-Color Partitions and Gordon-McIntosh Eight Order Mock Theta Functions
Authors: Agarwal A.K. , Sood G. 
Published: January 2020

In 2004, the first author gave the combinatorial interpretations of four mock theta functions of Srinivasa Ramanujan using $n$-color partitions which were introduced by himself and G.E. Andrews in 1987. In this paper we introduce a new class of partitions and call them "split $(n+t)$-color partitions". These new partitions generalize Agarwal-Andrews $(n+t)$-color partitions. We use these new combinatorial objects and give combinatorial meaning to two basic functions of Gordon-McIntosh found in 2000. They used these functions to establish the modular transformation formulas for certain eight order mock theta functions. The work done here has a great potential for future research.
Discrete Dirac Operators, Critical Embeddings and Ihara-Selberg Functions
Authors: Loebl Martin , Somberg Petr 
Published: January 2020

The aim of the paper is to formulate a discrete analogue of the claim made by Alvarez-Gaume et al., realizing the partition function of the free fermion on a closed Riemann surface of genus $g$ as a linear combination of $2^{2g}$ Pfaffians of Dirac operators. Let $G=(V,E)$ be a finite graph embedded in a closed Riemann surface $X$ of genus $g$, $x_e$ the collection of independent variables associated with each edge $e$ of $G$ (collected in one vector variable $x$) and $\S$ the set of all $2^{2g}$ spin-structures on $X$. We introduce $2^{2g}$ rotations $rot_s$ and $(2|E|\times 2|E|)$ matrices $\Delta(s)(x)$, $s\in \Sigma$, of the transitions between the oriented edges of $G$ determined by rotations $rot_s$. We show that the generating function of the even sets of edges of $G$, i.e., the Ising partition function, is a linear combination of the square roots of $2^{2g}$ Ihara-Selberg functions $I(\Delta(s)(x))$ also called Feynman functions. By a result of Foata and Zeilberger $I(\Delta(s)(x))=\det(I-\Delta'(s)(x))$, where $\Delta'(s)(x)$ is obtained from $\Delta(s)(x)$ by replacing some entries by $0$. Thus each Feynman function is computable in a polynomial time. We suggest that in the case of critical embedding of a bipartite graph $G$, the Feynman functions provide suitable discrete analogues for the Pfaffians of Dirac operators.
Generalized Spectral Characterization of Graphs Revisited
Authors: Wang Wei 
Published: January 2020

A graph $G$ is said to be determined by its generalized spectrum (DGS for short) if for any graph $H$, $H$ and $G$ are cospectral with cospectral complements implies that $H$ is isomorphic to $G$. Wang and Xu (2006) gave some methods for determining whether a family of graphs are DGS. In this paper, we shall review some of the old results and present some new ones along this line of research.More precisely, let $A$ be the adjacency matrix of a graph $G$, and let $W=[e,Ae,\cdots,A^{n-1}e]$ ($e$ is the all-one vector) be its walk-matrix. Denote by $\mathcal{G}_n$ the set of all graphs on $n$ vertices with $\det(W)\neq 0$. We define a large family of graphs $$\mathcal{F}_n=\{G\in{\mathcal{G}_n}|\frac{\det(W)}{2^{\lfloorn/2\rfloor}}\mbox{is square-free and }2^{\lfloorn/2\rfloor+1}\not|\det(W)\}$$ (which may have positive density among all graphs, as suggested by some numerical experiments). The main result of the paper shows that for any graph $G\in {\mathcal{F}_n}$, if there is a rational orthogonal matrix $Q$ with $Qe=e$ such that $Q^TAQ$ is a (0,1)-matrix, then $2Q$ must be an integral matrix (and hence, $Q$ has well-known structures). As a consequence, we get the conclusion that almost all graphs in $\mathcal{F}_n$ are DGS.
Rainbow Path and Color Degree in Edge Colored Graphs
Authors: Das Anita , Subrahmanya S. V. , Suresh P. 
Published: January 2020

Let $G$ be an edge colored graph. A rainbow pathin $G$ is a path in which all the edges are colored with distinct colors. Let $d^c(v)$ be the color degree of a vertex $v$ in $G$, i.e. the number of distinct colors present on the edges incident on the vertex $v$. Let $t$ be the maximum length of a rainbow path in $G$. Chen and Li (2005) showed that if $d^c \geq k \,\, (k\geq 8)$, for every vertex $v$ of $G$, then $t \geq \left \lceil \frac{3 k}{5}\right \rceil + 1$. Unfortunately, the proof by Chen and Li is very long and comes to about 23 pages in the journal version. Chen and Li states in their paper that it was conjectured by Akira Saito, that $t \ge \left \lceil \frac {2k} {3} \right \rceil$. They also state in their paper that they believe $t \ge k - c$ for some constant $c$. In this note, we give a short proof to show that $t \ge \left \lceil \frac{3 k}{5}\right \rceil$, using an entirely different method. Our proof is only about 2 pages long. The draw-back is that our bound is less by 1, than the bound given by Chen and Li. We hope that the new approach adopted in this paper would eventually lead to the settlement of the conjectures by Saito and/or Chen and Li.
The Concavity and Convexity of the Boros-Moll Sequences
Authors: Xia Ernest X.W. 
Published: January 2020

In their study of a quartic integral, Boros and Moll discovered a special class of sequences, which is called the Boros–Moll sequences. In this paper, we consider the concavity and convexity of the Boros–Moll sequences $\{d_i(m)\}_{i=0}^m$. We show that for any integer $m\geq 6$, there exist two positive integers $t_0(m)$ and $t_1(m)$ such that $d_i(m)+d_{i+2}(m)>2d_{i+1}(m)$ for $i\in [0,t_0(m)]\bigcup[t_1(m),m-2]$ and $d_i(m)+d_{i+2}(m) < 2d_{i+1}(m)$ for $i\in [t_0(m)+1,t_1(m)-1]$. When $m$ is a square, we find $t_0(m)=\frac{m-\sqrt{m}-4}{2}$ and $t_1(m) =\frac{m+\sqrt{m}-2}{2}$. As a corollary of our results, we show that \[\lim_{m\rightarrow +\infty }\frac{{\rm card}\{i|d_i(m)+d_{i+2}(m)< 2d_{i+1}(m), 0\leq i \leq m-2\}}{\sqrt{m}}=1. \]
The Topology of Competitively Constructed Graphs
Authors: Frieze Alan , Pegden Wesley 
Published: January 2020

We consider a simple game, the $k$-regular graph game, in which players take turns adding edges to an initially empty graph subject to the constraint that the degrees of vertices cannot exceed $k$. We show a sharp topological threshold for this game: for the case $k=3$ a player can ensure the resulting graph is planar, while for the case $k=4$, a player can force the appearance of arbitrarily large clique minors.