Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFast Strategies in Waiter-Client Games on $K_n$
97
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Waiter-Client games are played on some hypergraph $(X,mathcal{F})$, where $mathcal{F}$ denotes the family of winning sets. For some bias $b$, during each round of such a game Waiter offers to Client $b+1$ elements of $X$, of which Client claims one for himself while the rest go to Waiter. Proceeding like this Waiter wins the game if she forces Client to claim all the elements of any winning set from $mathcal{F}$. In this paper we study fast strategies for several Waiter-Client games played on the edge set of the complete graph, i.e. $X=E(K_n)$, in which the winning sets are perfect matchings, Hamilton cycles, pancyclic graphs, fixed spanning trees or factors of a given graph.
rate research
Read More
The Harary--Hill conjecture, still open after more than 50 years, asserts that the crossing number of the complete graph $K_n$ is $ H(n) = frac 1 4 leftlfloorfrac{mathstrut n}{mathstrut 2}rightrfloor leftlfloorfrac{mathstrut n-1}{mathstrut 2}rightrfloor leftlfloorfrac{mathstrut n-2}{mathstrut 2}rightrfloor leftlfloorfrac{mathstrut n-3}{mathstrut 2}right rfloor$. Abrego et al. introduced the notion of shellability of a drawing $D$ of $K_n$. They proved that if $D$ is $s$-shellable for some $sgeqlfloorfrac{n}{2}rfloor$, then $D$ has at least $H(n)$ crossings. This is the first combinatorial condition on a drawing that guarantees at least $H(n)$ crossings. In this work, we generalize the concept of $s$-shellability to bishellability, where the former implies the latter in the sense that every $s$-shellable drawing is, for any $b leq s-2$, also $b$-bishellable. Our main result is that $(lfloor frac{n}{2} rfloor!-!2)$-bishellability of a drawing $D$ of $K_n$ also guarantees, with a simpler proof than for $s$-shellability, that $D$ has at least $H(n)$ crossings. We exhibit a drawing of $K_{11}$ that has $H(11)$ crossings, is 3-bishellable, and is not $s$-shellable for any $sgeq5$. This shows that we have properly extended the class of drawings for which the Harary-Hill Conjecture is proved. Moreover, we provide an infinite family of drawings of $K_n$ that are $(lfloor frac{n}{2} rfloor!-!2)$-bishellable, but not $s$-shellable for any $sgeqlfloorfrac{n}{2}rfloor$.
In 2015 Bloom and Liebenau proved that $K_n$ and $K_n+K_{n-1}$ possess the same $2$-Ramsey graphs for all $ngeq 3$ (with a single exception for $n=3$). In the following we give a simple proof that $K_n$ and $K_n+K_{n-1}$ possess the same $r$-Ramsey graphs for all $n, rgeq 3$.
In studying properties of simple drawings of the complete graph in the sphere, two natural questions arose for us: can an edge have multiple segments on the boundary of the same face? and is each face the intersection of sides of 3-cycles? The second is asserted to be obvious in two previously published articles, but when asked, authors of both papers were unable to provide a proof. We present a proof. The first is quite easily proved and the technique yields a third, even simpler, fact: no three edges at a vertex all have internal points incident with the same face.
By now, the Maker-Breaker connectivity game on a complete graph $K_n$ or on a random graph $Gsim G_{n,p}$ is well studied. Recently, London and Pluhar suggested a variant in which Maker always needs to choose her edges in such a way that her graph stays connected. By their results it follows that for this connected version of the game, the threshold bias on $K_n$ and the threshold probability on $Gsim G_{n,p}$ for winning the game drastically differ from the corresponding values for the usual Maker-Breaker version, assuming Makers bias to be $1$. However, they observed that the threshold biases of bo
We study a game where two players take turns selecting points of a convex geometry until the convex closure of the jointly selected points contains all the points of a given winning set. The winner of the game is the last player able to move. We develop a structure theory for these games and use it to determine the nim number for several classes of convex geometries, including one-dimensional affine geometries, vertex geometries of trees, and games with a winning set consisting of extreme points.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
