16 results
Now showing1 - 10 of 16
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , The size-Ramsey number of powers of pathsGiven graphs G and H and a positive integer q, say that G is q-Ramsey for H, denoted G → (H) q , if every q-coloring of the edges of G contains a monochromatic copy of H. The size-Ramsey number (Formula presented.) of a graph H is defined to be (Formula presented.). Answering a question of Conlon, we prove that, for every fixed k, we have (Formula presented.), where P nk is the kth power of the n-vertex path P n (ie, the graph with vertex set V(P n ) and all edges u, v such that the distance between u and v in P n is at most k). Our proof is probabilistic, but can also be made constructive.Publicationtype: Journal Article209 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Colourings without monochromatic disjoint pairs(2018-05); ; The typical extremal problem asks how large a structure can be without containing a forbidden substructure. The Erdős–Rothschild problem, introduced in 1974 by Erdős and Rothschild in the context of extremal graph theory, is a coloured extension, asking for the maximum number of colourings a structure can have that avoid monochromatic copies of the forbidden substructure. The celebrated Erdős–Ko–Rado theorem is a fundamental result in extremal set theory, bounding the size of set families without a pair of disjoint sets, and has since been extended to several other discrete settings. The Erdős–Rothschild extensions of these theorems have also been studied in recent years, most notably by Hoppen, Koyakayawa and Lefmann for set families, and Hoppen, Lefmann and Odermann for vector spaces. In this paper we present a unified approach to the Erdős–Rothschild problem for intersecting structures, which allows us to extend the previous results, often with sharp bounds on the size of the ground set in terms of the other parameters. In many cases we also characterise which families of vector spaces asymptotically maximise the number of Erdős–Rothschild colourings, thus addressing a conjecture of Hoppen, Lefmann and Odermann.Publicationtype: Journal Article158 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , How fast can Maker win in fair biased games?(2018-01-01); We study (a:a) Maker–Breaker games played on the edge set of the complete graph on n vertices. In the following four games — perfect matching game, Hamilton cycle game, star factor game and path factor game, our goal is to determine the least number of moves which Maker needs in order to win these games. Moreover, for all games except for the star factor game, we show how first player can win in the strong version of these games.Publicationtype: Journal Article191 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , A Dirac-type theorem for Hamilton Berge cycles in random hypergraphs(2016-10-01); ; A Hamilton Berge cycle of a hypergraph on n vertices is an alternating sequence (v1,e1,v2,…,vn,en) of distinct vertices v1,…,vn and distinct hyperedges e1,…,en such that v1,vn⊆en and vi,vi+1⊆ei for every i∈[n−1]. We prove a Dirac-type theorem for Hamilton Berge cycles in random r-uniform hypergraphs by showing that for every integer r≥3 there exists k=k(r) such that for every γ>0 and p≥logk(r)(n)nr−1 asymptotically almost surely every spanning subhypergraph H⊆H(r)(n,p) with minimum vertex degree δ1(H)≥(12r−1+γ)p(n−1r−1) contains a Hamilton Berge cycle. The minimum degree condition is asymptotically tight and the bound on p is optimal up to possibly the logarithmic factor. As a corollary this gives a new upper bound on the threshold of H(r)(n,p) with respect to Berge Hamiltonicity.Publicationtype: Journal Article216 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , On sets not belonging to algebras and rainbow matchings in graphsMotivated by a question of Grinblat, we study the minimal number v(n) that satisfies the following. If A1,…,An are equivalence relations on a set X such that for every i∈[n] there are at least v(n) elements whose equivalence classes with respect to Ai are nontrivial, then A1,…,An contain a rainbow matching, i.e. there exist 2n distinct elements x1,y1,…,xn,yn∈X with xi∼Aiyi for each i∈[n]. Grinblat asked whether v(n)=3n−2 for every n≥4. The best-known upper bound was v(n)≤16n/5+O(1) due to Nivasch and Omri. Transferring the problem into the setting of edge-coloured multigraphs, we affirm Grinblat's question asymptotically, i.e. we show that v(n)=3n+o(n).Publicationtype: Journal Article135 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , A non-trivial upper bound on the threshold bias of the Oriented-cycle gameIn the Oriented-cycle game, introduced by Bollobás and Szabó [7], two players, called OMaker and OBreaker, alternately direct edges of Kn. OMaker directs exactly one previously undirected edge, whereas OBreaker is allowed to direct between one and b previously undirected edges. OMaker wins if the final tournament contains a directed cycle, otherwise OBreaker wins. Bollobás and Szabó [7] conjectured that for a bias as large as n−3 OMaker has a winning strategy if OBreaker must take exactly b edges in each round. It was shown recently by Ben-Eliezer, Krivelevich and Sudakov [6], that OMaker has a winning strategy for this game whenever b<n/2−1. In this paper, we show that OBreaker has a winning strategy whenever b>5n/6+1. Moreover, in case OBreaker is required to direct exactly b edges in each move, we show that OBreaker wins for b⩾19n/20, provided that n is large enough. This refutes the conjecture by Bollobás and Szabó.Publicationtype: Journal Article151 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Creating cycles in Walker-Breaker gamesWe consider biased (1:b) Walker-Breaker games: Walker and Breaker alternately claim edges of the complete graph Kn, Walker taking one edge and Breaker claiming b edges in each round, with the constraint that Walker needs to choose her edges according to a walk. As questioned in a paper by Espig, Frieze, Krivelevich and Pegden, we study how long a cycle Walker is able to create and for which biases b Walker has a chance to create a cycle of given constant length.Publicationtype: Journal Article99 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , An improved bound on the sizes of matchings guaranteeing a rainbow matching(2016-04-15); A conjecture by Aharoni and Berger states that every family of n matchings of size n + 1 in a bipartite multigraph contains a rainbow matching of size n. In this paper we prove that matching sizes of (3/2 + o(1))n suffice to guarantee such a rainbow matching, which is asymptotically the same bound as the best-known one in the case where we only aim to find a rainbow matching of size n – 1. This improves previous results by Aharoni, Charbit and Howard, and Kotlar and Ziv.Publicationtype: Journal Article90 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Minimum Degrees and Codegrees of Ramsey-Minimal 3-Uniform HypergraphsA uniform hypergraph H is called k-Ramsey for a hypergraph F if, no matter how one colours the edges of H with k colours, there is always a monochromatic copy of F. We say that H is k-Ramsey-minimal for F if H is k-Ramsey for F but every proper subhypergraph of H is not. Burr, ErdÅ's and Lovasz studied various parameters of Ramsey-minimal graphs. In this paper we initiate the study of minimum degrees and codegrees of Ramsey-minimal 3-uniform hypergraphs. We show that the smallest minimum vertex degree over all k-Ramsey-minimal 3-uniform hypergraphs for Kt(3) is exponential in some polynomial in k and t. We also study the smallest possible minimum codegree over 2-Ramsey-minimal 3-uniform hypergraphs.Publicationtype: Journal Article111 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , The Random Graph Intuition for the Tournament Game(2016-01-01); ; In the tournament game two players, called Maker and Breaker, alternately take turns in claiming an unclaimed edge of the complete graph Kn and selecting one of the two possible orientations. Before the game starts, Breaker fixes an arbitrary tournament Tk on k vertices. Maker wins if, at the end of the game, her digraph contains a copy of Tk; otherwise Breaker wins. In our main result, we show that Maker has a winning strategy for k = (2-o(1))log2 n, improving the constant factor in previous results of Beck and the second author. This is asymptotically tight since it is known that for k = (2-o(1))log2 n Breaker can prevent the underlying graph of Maker's digraph from containing a k-clique. Moreover, the precise value of our lower bound differs from the upper bound only by an additive constant of 12. We also discuss the question of whether the random graph intuition, which suggests that the threshold for k is asymptotically the same for the game played by two 'clever' players and the game played by two 'random' players, is supported by the tournament game. It will turn out that, while a straightforward application of this intuition fails, a more subtle version of it is still valid. Finally, we consider the orientation game version of the tournament game, where Maker wins the game if the final digraph-also containing the edges directed by Breaker-possesses a copy of Tk. We prove that in that game Breaker has a winning strategy for k = (4 + o(1))log2 n.Publicationtype: Journal Article100