Abstract We study biased Maker/Breaker games on the edges of complete graph, as introduced by Chvátal and Erdős. show that Maker, occupying one edge in each his turns, can build a spanning tree, even if Breaker occupies b ≤ (1 − o (1)) · $ {n \over \ln n} turn. This improves result Beck, is asymptotically best possible witnessed Breaker‐strategy also give strategy for Maker to occupy graph with minimum degree c (where = ( n ) slowly growing function while playing against who takes earlier...

We construct unsatisfiable k-CNF formulas where every clause has k distinct literals and variable appears in at most (2/e +o(1)) 2k/k clauses. The lopsided Local Lemma shows that our result is asymptotically best possible: formula 2k+1/e(k+1) − 1 clauses satisfiable. determination of this extremal function particularly important as it represents the value k-SAT problem exhibits its complexity hardness jump: from having instance being a YES-instance becomes NP-hard just by allowing each to...

The main contribution of this paper is a new approach for enumerating Hamilton cycles in bounded degree graphs – deriving thereby extremal bounds.

The Local Lemma is a fundamental tool of probabilistic combinatorics and theoretical computer science, yet there are hardly any natural problems known where it provides an asymptotically tight answer. main theme our article to identify several these problems, among them couple widely studied extremal functions related certain restricted versions the k -SAT problem, does give essentially optimal answers. As contribution, we construct unsatisfiable -CNF formulas every clause has distinct...

We describe an algorithm which enumerates all Hamilton cycles of a given 3-regular $n$-vertex graph in time $O(1.276^{n})$, improving on Eppstein's previous bound. The resulting new upper bound $O(1.276^{n})$ for the maximum number graphs gets close to best known lower $\Omega(1.259^{n})$. Our method differs from that he considers each step and modifies it, while we fix (at very beginning) one cycle $C$ then proceed around $C$, successively producing partial cycles.

We construct unsatisfiable k-CNF formulas where every clause has k distinct literals and variable appears in at most clauses. The lopsided Local Lemma shows that our result is asymptotically best possible: formula clauses satisfiable. determination of this extremal function particularly important as it represents the value k-SAT problem exhibits its complexity hardness jump: from having instance being a YES-instance becomes NP-hard just by allowing each to occur one more clause.The...

In a properly edge colored graph, subgraph using every color at most once is called rainbow. this thesis, we study rainbow cycles and paths in proper colorings of complete graphs, prove that coloring K_n, there path on (3/4-o(1))n vertices, improving the previously best bound (2n+1)/3 from Gyarfas Mhalla. Similarly, k-rainbow K_n no more than k times. We (1-2/(k+1)!)n vertices.

In the tournament game two players, called Maker and Breaker, alternately take turns in claiming an unclaimed edge of complete graph on n vertices selecting one possible orientations. Before starts, Breaker fixes arbitrary T_k k vertices. wins if, at end game, her digraph contains a copy T_k; otherwise wins. our main result, we show that has winning strategy for = (2-o(1))log_2 n, improving constant factor previous results Beck second author. This is asymptotically tight since it known can...

We prove # P -completeness for counting the number of forests in regular graphs and chordal graphs. also present algorithms this problem, running O *(1.8494 m ) time 3-regular graphs, *(1.9706 unit interval where is edges graph *-notation ignores a polynomial factor. The can be generalized to Tutte computation.

We study Maker/Breaker games on the edges of sparse graphs. Maker and Breaker take turns at claiming previously unclaimed a given graph H . aims to occupy target G tries prevent from achieving his goal. show that for every d there is constant c = c(d) with property n vertices maximum degree most cn such has strategy copy in game This result about game-theoretic variant size Ramsey number. For , $\hat{r}'(G)$ defined as smallest number M which exists In this language, our yields connected...

We consider the following cake cutting game: Alice chooses a set P of n points in square (cake) [0,1]^2, where (0,0) is P; Bob cuts out axis-parallel rectangles with disjoint interiors, each them having point as lower left corner; keeps rest. It has been conjectured that can always secure at least half cake. This remains unsettled, and it not even known whether get any positive fraction independent n. prove if force Bob's share to tend zero, then she must use very many points; namely,...

We study Maker/Breaker games on the edges of sparse graphs. Maker and Breaker take turns in claiming previously unclaimed a given graph H. aims to occupy target G tries prevent from achieving his goal. define function f show that for every d-regular n vertices there is H with at most f(d)n such can copy game