Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBin-based pairing strategies for the Maker-Breaker game on the boolean hypercube with subcubes as winning sets
110
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider the Maker-Breaker positional game on the vertices of the $n$-dimensional hypercube ${0,1}^n$ with $k$-dimensional subcubes as winning sets. We describe a pairing strategy which allows Breaker to win when $k = n/4 +1$ in the case where $n$ is a power of 4. Our results also imply the general result that there is a Breakers win pairing strategy for any $n geq 3$ if $k = leftlfloorfrac{3}{7}nrightrfloor +1$.
rate research
Read More
We investigate games played between Maker and Breaker on an infinite complete graph whose vertices are coloured with colours from a given set, each colour appearing infinitely often. The players alternately claim edges, Makers aim being to claim all edges of a sufficiently colourful infinite complete subgraph and Breakers aim being to prevent this. We show that if there are only finitely many colours then Maker can obtain a complete subgraph in which all colours appear infinitely often, but that Breaker can prevent this if there are infinitely many colours. Even when there are infinitely many colours, we show that Maker can obtain a complete subgraph in which infinitely many of the colours each appear infinitely often.
The convex grabbing game is a game where two players, Alice and Bob, alternate taking extremal points from the convex hull of a point set on the plane. Rational weights are given to the points. The goal of each player is to maximize the total weight over all points that they obtain. We restrict the setting to the case of binary weights. We show a construction of an arbitrarily large odd-sized point set that allows Bob to obtain almost 3/4 of the total weight. This construction answers a question asked by Matsumoto, Nakamigawa, and Sakuma in [Graphs and Combinatorics, 36/1 (2020)]. We also present an arbitrarily large even-sized point set where Bob can obtain the entirety of the total weight. Finally, we discuss conjectures about optimum moves in the convex grabbing game for both players in general.
In the $d$-dimensional hypercube bin packing problem, a given list of $d$-dimensional hypercubes must be packed into the smallest number of hypercube bins. Epstein and van Stee [SIAM J. Comput. 35 (2005)] showed that the asymptotic performance ratio $rho$ of the online bounded space variant is $Omega(log d)$ and $O(d/log d)$, and conjectured that it is $Theta(log d)$. We show that $rho$ is in fact $Theta(d/log d)$, using probabilistic arguments.
We determine the asymptotics of the number of independent sets of size $lfloor beta 2^{d-1} rfloor$ in the discrete hypercube $Q_d = {0,1}^d$ for any fixed $beta in [0,1]$ as $d to infty$, extending a result of Galvin for $beta in [1-1/sqrt{2},1]$. Moreover, we prove a multivariate local central limit theorem for structural features of independent sets in $Q_d$ drawn according to the hard core model at any fixed fugacity $lambda>0$. In proving these results we develop several general tools for performing combinatorial enumeration using polymer models and the cluster expansion from statistical physics along with local central limit theorems.
The main result of the present paper is a new lower bound on the number of Boolean bent functions. This bound is based on a modification of the Maiorana--McFarland family of bent functions and recent progress in the estimation of the number of transversals in latin squares and hypercubes. In addition, we find the asymptotics of the logarithm of the numbers of partitions of the Boolean hypercube into $2$-dimensional linear and affine subspaces.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
