Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLinear Bounds for Cycle-free Saturation Games
62
0
0.0
(
0
)
Added by
Tom\\'a\\v{s} Masa\\v{r}\\'ik
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a family of graphs $mathcal{F}$, we define the $mathcal{F}$-saturation game as follows. Two players alternate adding edges to an initially empty graph on $n$ vertices, with the only constraint being that neither player can add an edge that creates a subgraph in $mathcal{F}$. The game ends when no more edges can be added to the graph. One of the players wishes to end the game as quickly as possible, while the other wishes to prolong the game. We let $textrm{sat}_g(n,mathcal{F})$ denote the number of edges that are in the final graph when both players play optimally. In general there are very few non-trivial bounds on the order of magnitude of $textrm{sat}_g(n,mathcal{F})$. In this work, we find collections of infinite families of cycles $mathcal{C}$ such that $textrm{sat}_g(n,mathcal{C})$ has linear growth rate.
rate research
Read More
We study F-saturation games, first introduced by Furedi, Reimer and Seress in 1991, and named as such by West. The main question is to determine the length of the game whilst avoiding various classes of graph, playing on a large complete graph. We show lower bounds on the length of path-avoiding games, and more precise results for short paths. We show sharp results for the tree avoiding game and the star avoiding game.
We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as a bridge between the existing monotone and general games. Using this game, we prove hazard-free formula size and depth lower bounds that are provably stronger than those possible by the standard technique of transferring results from monotone complexity in a black-box fashion. For the multiplexer function we give (1) a hazard-free formula of optimal size and (2) an improved low-depth hazard-free formula of almost optimal size and (3) a hazard-free formula with alternation depth $2$ that has optimal depth. We then use our optimal constructions to obtain an improved universal worst-case hazard-free formula size upper bound. We see our results as a significant step towards establishing hazard-free computation as an independent missing link between Boolean complexity and monotone complexity.
While there have been many results on lower bounds for Max Cut in unweighted graphs, the only lower bound for non-integer weights is that by Poljak and Turzik (1986). In this paper, we launch an extensive study of lower bounds for Max Cut in weighted graphs. We introduce a new approach for obtaining lower bounds for Weighted Max Cut. Using it, Probabilistic Method, Vizings chromatic index theorem, and other tools, we obtain several lower bounds for arbitrary weighted graphs, weighted graphs of bounded girth and triangle-free weighted graphs. We pose conjectures and open questions.
We study analogues of $mathcal{F}$-saturation games, first introduced by Furedi, Reimer and Seress in 1991, and named as such by West. We examine analogous games on directed graphs, and show tight results on the walk-avoiding game. We also examine an intermediate game played on undirected graphs, such that there exists an orientation avoiding a given family of directed graphs, and show bounds on the score. This last game is shown to be equivalent to a recent game studied by Hefetz, Krivelevich, Naor and Stojakovic, and we give new bounds for bias
Let $S$ be a set of positive integers, and let $D$ be a set of integers larger than $1$. The game $i$-Mark$(S,D)$ is an impartial combinatorial game introduced by Sopena (2016), which is played with a single pile of tokens. In each turn, a player can subtract $s in S$ from the pile, or divide the size of the pile by $d in D$, if the pile size is divisible by $d$. Sopena partially analyzed the games with $S=[1, t-1]$ and $D={d}$ for $d otequiv 1 pmod t$, but left the case $d equiv 1 pmod t$ open. We solve this problem by calculating the Sprague-Grundy function of $i$-Mark$([1,t-1],{d})$ for $d equiv 1 pmod t$, for all $t,d geq 2$. We also calculate the Sprague-Grundy function of $i$-Mark$({2},{2k + 1})$ for all $k$, and show that it exhibits similar behavior. Finally, following Sopenas suggestion to look at games with $|D|>1$, we derive some partial results for the game $i$-Mark$({1}, {2, 3})$, whose Sprague-Grundy function seems to behave erratically and does not show any clean pattern. We prove that each value $0,1,2$ occurs infinitely often in its SG sequence, with a maximum gap length between consecutive appearances.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
