Playing to Retain the Advantage ALON, NOGA; HEFETZ, DAN; KRIVELEVICH, MICHAEL
Combinatorics, probability & computing,
07/2010, Letnik:
19, Številka:
4
Journal Article
Recenzirano
Odprti dostop
Let P be a monotone increasing graph property, let G = (V, E) be a graph, and let q be a positive integer. In this paper, we study the (1: q) Maker–Breaker game, played on the edges of G, in which ...Maker's goal is to build a graph that satisfies the property P. It is clear that in order for Maker to have a chance of winning, G itself must satisfy P. We prove that if G satisfies P in some strong sense, that is, if one has to delete sufficiently many edges from G in order to obtain a graph that does not satisfy P, then Maker has a winning strategy for this game. We also consider a different notion of satisfying some property in a strong sense, which is motivated by a problem of Duffus, Łuczak and Rödl 6.
Let \(\tilde K_t\) denote the \(3\)-uniform linear clique of order \(t\). Given an even integer \(t \geq 4\), let \(M\) denote the asymmetric maximal density of \(\tilde K_t\) and \(\tilde K_{t/2}\). ...We prove that there exists a constant \(C>0\) such that, if \((H_n)_{n \in \mathbb{N}}\) is any sequence of dense \(3\)-uniform hypergraphs and \(p := p(n) \geq Cn^{-1/M}\), then $$ \lim_{n \to \infty} \PrH_n \cup R_n \to (\tilde K_t)_2 =1 $$ holds, whenever \(R_n \sim \mathbb{H}(n,p)\), where the latter denotes the binomial \(3\)-uniform random hypergraph distribution. We conjecture that this result uncovers the threshold for the property in question for \(t \geq 6\). The key tools of our proof are a new variant of the Strong Hypergraph Regularity Lemma along with a new Tuple Lemma accompanying it. Our variant incorporates both the strong and the weak hypergraph regularity lemmas into a single lemma; allowing for graph-like applications of the strong lemma to be carried out in \(3\)-uniform hypergraphs.
The {\em discrepancy} of a matrix $M \in \mathbb{R}^{d \times n}$ is given by
$\mathrm{DISC}(M) := \min_{\boldsymbol{x} \in \{-1,1\}^n}
\|M\boldsymbol{x}\|_\infty$. An outstanding conjecture, ...attributed to Koml\'os,
stipulates that $\mathrm{DISC}(M) = O(1)$, whenever $M$ is a Koml\'os matrix,
that is, whenever every column of $M$ lies within the unit sphere. Our main
result asserts that $\mathrm{DISC}(M + R/\sqrt{d}) = O(d^{-1/2})$ holds
asymptotically almost surely, whenever $M \in \mathbb{R}^{d \times n}$ is
Koml\'os, $R \in \mathbb{R}^{d \times n}$ is a Rademacher random matrix, $d =
\omega(1)$, and $n = \omega(d \log d)$. The factor $d^{-1/2}$ normalising $R$
is essentially best possible and the dependency between $n$ and $d$ is
asymptotically best possible. Our main source of inspiration is a result by
Bansal, Jiang, Meka, Singla, and Sinha (ICALP 2022). They obtained an assertion
similar to the one above in the case that the smoothing matrix is Gaussian.
They asked whether their result can be attained with the optimal dependency $n
= \omega(d \log d)$ in the case of Bernoulli random noise or any other types of
discretely distributed noise; the latter types being more conducive for
Smoothed Analysis in other discrepancy settings such as the Beck-Fiala problem.
For Bernoulli noise, their method works if $n = \omega(d^2)$. In the case of
Rademacher noise, we answer the question posed by Bansal, Jiang, Meka, Singla,
and Sinha. Our proof builds upon their approach in a strong way and provides a
discrete version of the latter. Breaking the $n = \omega(d^2)$ barrier and
reaching the optimal dependency $n = \omega(d \log d)$ for Rademacher noise
requires additional ideas expressed through a rather meticulous counting
argument, incurred by the need to maintain a high level of precision all
throughout the discretisation process.
Avoider–Enforcer games Hefetz, Dan; Krivelevich, Michael; Szabó, Tibor
Journal of combinatorial theory. Series A,
07/2007, Letnik:
114, Številka:
5
Journal Article
Recenzirano
Odprti dostop
Let
p and
q be positive integers and let
H
be any hypergraph. In a
(
p
,
q
,
H
)
Avoider–Enforcer game two players, called Avoider and Enforcer, take turns selecting previously unclaimed vertices of
...H
. Avoider selects
p vertices per move and Enforcer selects
q vertices per move. Avoider loses if he claims all the vertices of some hyperedge of
H
; otherwise Enforcer loses. We prove a sufficient condition for Avoider to win the
(
p
,
q
,
H
)
game. We then use this condition to show that Enforcer can win the
(
1
,
q
)
perfect matching game on
K
2
n
for every
q
⩽
c
n
/
log
n
for an appropriate constant
c, and the
(
1
,
q
)
Hamilton cycle game on
K
n
for every
q
⩽
c
n
log
log
log
log
n
/
log
n
log
log
log
n
for an appropriate constant
c. We also determine exactly those values of
q for which Enforcer can win the
(
1
,
q
)
connectivity game on
K
n
. This result is quite surprising as it substantially differs from its Maker–Breaker analog. Our method extends easily to improve a result of Lu X. Lu, A note on biased and non-biased games, Discrete Appl. Math. 60 (1995) 285–291, regarding forcing an opponent to pack many pairwise edge disjoint spanning trees in his graph.
Given a tree T=(V,E) on n vertices, we consider the (1:q) Maker-Breaker tree embedding game Tn. The board of this game is the edge set of the complete graph on n vertices. Maker wins Tn if and only ...if he is able to claim all edges of a copy of T. We prove that there exist real numbers α,ε>0 such that, for sufficiently large n and for every tree T on n vertices with maximum degree at most nε, Maker has a winning strategy for the (1:q) game Tn, for every q⩽nα. Moreover, we prove that Maker can win this game within n+o(n) moves which is clearly asymptotically optimal.
Extremal properties of sparse graphs, randomly perturbed by the binomial random graph are considered. It is known that every \(n\)-vertex graph \(G\) contains a complete minor of order ...\(\Omega(n/\alpha(G))\). We prove that adding \(\xi n\) random edges, where \(\xi > 0\) is arbitrarily small yet fixed, to an \(n\)-vertex graph \(G\) satisfying \(\alpha(G) \leq \zeta(\xi)n\) asymptotically almost surely results in a graph containing a complete minor of order \(\tilde \Omega \left( n/\sqrt{\alpha(G)}\right)\); this result is tight up to the implicit logarithmic terms. For complete topological minors, we prove that there exists a constant \(C>0\) such that adding \(C n\) random edges to a graph \(G\) satisfying \(\delta(G) = \omega(1)\), asymptotically almost surely results in a graph containing a complete topological minor of order \(\tilde \Omega(\min\{\delta(G),\sqrt{n}\})\); this result is tight up to the implicit logarithmic terms. Finally, extending results of Bohman, Frieze, Krivelevich, and Martin for the dense case, we analyse the asymptotic behaviour of the vertex-connectivity and the diameter of randomly perturbed sparse graphs.
Avoider–Enforcer: The rules of the game Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš ...
Journal of combinatorial theory. Series A,
02/2010, Letnik:
117, Številka:
2
Journal Article
Recenzirano
Odprti dostop
An Avoider–Enforcer game is played by two players, called Avoider and Enforcer, on a hypergraph
F
⊆
2
X
. The players claim previously unoccupied elements of the board
X in turns. Enforcer
wins if ...Avoider claims all vertices of some element of
F
, otherwise Avoider wins. In a more general version of the game a
bias b is introduced to level up the players' chances of winning; Avoider claims one element of the board in each of his moves, while Enforcer responds by claiming
b elements. This traditional set of rules for Avoider–Enforcer games is known to have a shortcoming: it is not bias monotone.
We relax the traditional rules in a rather natural way to obtain bias monotonicity. We analyze this new set of rules and compare it with the traditional ones to conclude some surprising results. In particular, we show that under the new rules the threshold bias for both the connectivity and Hamiltonicity games, played on the edge set of the complete graph
K
n
, is asymptotically equal to
n
/
log
n
. This coincides with the asymptotic threshold bias of the same game played by two “random” players.
Global Maker–Breaker games on sparse graphs Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš ...
European journal of combinatorics,
02/2011, Letnik:
32, Številka:
2
Journal Article
Recenzirano
Odprti dostop
In this paper we consider Maker–Breaker games, played on the edges of
sparse graphs. For a given graph property
P
we seek a graph (board of the game) with the smallest number of edges on which Maker ...can build a subgraph that satisfies
P
. In this paper we focus on
global properties. We prove the following results: (1) for the positive minimum degree game, there is a winning board with
n
vertices and about
10
n
/
7
edges, on the other hand, at least
11
n
/
8
edges are required; (2) for the spanning
k
-connectivity game, there is a winning board with
n
vertices and
(
1
+
o
k
(
1
)
)
k
n
edges; (3) for the Hamiltonicity game, there is a winning board of constant average degree; (4) for a tree
T
on
n
vertices of bounded maximum degree
Δ
, there is a graph
G
on
n
vertices and at most
f
(
Δ
)
⋅
n
edges, on which Maker can construct a copy of
T
. We also discuss biased versions of these games and argue that the picture changes quite drastically there.
Planarity, Colorability, and Minor Games Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš ...
SIAM journal on discrete mathematics,
01/2008, Letnik:
22, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Let $m$ and $b$ be positive integers, and let $F$ be a hypergraph. In an $(m,b)$ Maker-Breaker game $F$ two players, called Maker and Breaker, take turns selecting previously unclaimed vertices of ...$F$. Maker selects $m$ vertices per move, and Breaker selects $b$ vertices per move. The game ends when every vertex has been claimed by one of the players. Maker wins if he claims all of the vertices of some hyperedge of $F$; otherwise Breaker wins. An $(m,b)$ Avoider-Enforcer game $F$ is played in a similar way. The only difference is in the determination of the winner: Avoider loses if he claims all of the vertices of some hyperedge of $F$; otherwise Enforcer loses. In this paper we consider the Maker-Breaker and Avoider-Enforcer versions of the planarity game, the $k$-colorability game, and the $K_t$-minor game.
PDF
