BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Tomasz Łuczak appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
For graphs $H_1,H_2$ by $r^*(H_1,H_2)$ we denote the minimum number of edges in a graph $G$ on $r(H_1,H_2)$ vertices such that $G\to (H_1,H_2)$. We show that for each pair of natural numbers $k,n$, $k\le n$, where $k$ is odd and $n$ is large enough, we have $$r^*(C_n,C_k)=\lceil (n+1)(2n-1)/2\rceil \,.$$
Given positive integers $n\ge s$, we let ${\mathrm{ex}}(n,s)$ denote the maximum number of edges in a triangle-free graph $G$ on $n$ vertices with $α(G)\le s$. In the early sixties Andrásfai conjectured that for $n/3<s<n/2$ the function ${\mathrm{ex}}(n, s)$ is piecewise quadratic with critical values at $s/n={k}/({3k-1})$. We confirm that this is indeed the case whenever $s/n$ is slightly larger than a critical value, thus determining ${\mathrm{ex}}(n,s)$ for all $n$ and $s$ such that $s/n\in [{k}/({3k-1}), {k}/({3k-1})+γ_k]$, where $γ_k=Θ(k^{-6})$.
We show that for every $η>0$, there exists $n_0$ such that for every even $n$, $n\ge n_0$, and every graph $G$ with $(2+η)n$ vertices and minimum degree at least $(7/4+4η)n$, each colouring of the edges of $G$ with three colours results in a monochromatic cycle of length $n$.
One of the oldest results in modern graph theory, due to Mantel, asserts that every triangle-free graphs on $n$ vertices has at most $\lfloor n^2/4\rfloor$ edges. About half a century later Andrásfai studied dense triangle-free graphs and proved that the largest triangle-free graphs on $n$ vertices without independent sets of size $αn$, where $2/5\le α< 1/2$, are blow-ups of the pentagon. More than 50 further years have elapsed since Andrásfai's work. In this article we make the next step towards understanding the structure of dense triangle-free graphs without large independent sets. Notably, we determine the maximum size of triangle-free graphs~$G$ on $n$ vertices with $α(G)\ge 3n/8$ and state a conjecture on the structure of the densest triangle-free graphs $G$ with $α(G) > n/3$. We remark that the case $α(G) \le n/3$ behaves differently, but due to the work of Brandt this situation is fairly well understood.
The random triangular group $Γ(n,p)$ is the group given by a random group presentation with $n$ generators in which every relator of length three is present independently with probability $p$. We show that in the evolution of $Γ(n,p)$ the property of collapsing to the trivial group admits a very sharp threshold.
A sequence $S$ is called anagram-free if it contains no consecutive symbols $r_1 r_2\dots r_k r_{k+1} \dots r_{2k}$ such that $r_{k+1} \dots r_{2k}$ is a permutation of the block $r_1 r_2\dots r_k$. Answering a question of Erdős and Brown, Keränen constructed an infinite anagram-free sequence on four symbols. Motivated by the work of Alon, Grytczuk, Hałuszczak and Riordan, we consider a natural generalisation of anagram-free sequences for graph colorings. A coloring of the vertices of a given graph $G$ is called anagram-free if the sequence of colors on any path in $G$ is anagram-free. We call the minimal number of colors needed for such a coloring the anagram-chromatic number of $G$. In this paper we study the anagram-chromatic number of several classes of graphs like trees, minor-free graphs and bounded-degree graphs. Surprisingly, we show that there are bounded-degree graphs (such as random regular graphs) in which anagrams cannot be avoided unless we basically give each vertex a separate color.
The random $2$-dimensional simplicial complex process starts with a complete graph on $n$ vertices, and in every step a new $2$-dimensional face, chosen uniformly at random, is added. We prove that with probability tending to $1$ as $n\to\infty$, the first homology group over $\mathbb Z$ vanishes at the very moment when all the edges are covered by triangular faces.
We consider the problem of finding the optimal upper bound for the tail probability of a sum of $k$ nonnegative, independent and identically distributed random variables with given mean $x$. For $k=1$ the answer is given by Markov's inequality and for $k=2$ the solution was found by Hoeffding and Shrikhande in 1955. We solve the problem for $k=3$ as well as for general $k$ and $x\leq1/(2k-1)$ by showing that it follows from the fractional version of an extremal graph theory problem of Erdős on matchings in hypergraphs.
We show that if we color the hyperedges of the complete $3$-uniform complete graph on $2n+\sqrt{18n+1}+2$ vertices with $n$ colors, then one of the color classes contains a loose path of length three.
It is shown that a.a.s. as soon as a Kronecker graph becomes connected its diameter is bounded by a constant.
For positive integers $n$ and $q$ and a monotone graph property $\cA$, we consider the two player, perfect information game $\WC(n,q,\cA)$, which is defined as follows. The game proceeds in rounds. In each round, the first player, called Waiter, offers the second player, called Client, $q+1$ edges of the complete graph $K_n$ which have not been offered previously. Client then chooses one of these edges which he keeps and the remaining $q$ edges go back to Waiter. If at the end of the game, the graph which consists of the edges chosen by Client satisfies the property $\cA$, then Waiter is declared the winner; otherwise Client wins the game. In this paper we study such games (also known as Picker-Chooser games) for a variety of natural graph theoretic parameters, such as the size of a largest component or the length of a longest cycle. In particular, we describe a phase transition type phenomenon which occurs when the parameter $q$ is close to $n$ and is reminiscent of phase transition phenomena in random graphs. Namely, we prove that if $q \leq (1 - \varepsilon) n$, then Client can avoid connected components of order $c \varepsilon^{-2} \ln n$ for some absolute constant $c > 0$, whereas, for $q \geq (1 + \varepsilon) n$, Waiter can force a giant, linearly sized, connected component in Client's graph. We also prove that Waiter can force Client's graph to be pancyclic for every $q \leq c n$, where $c > 0$ is an appropriate constant.
Given a fixed graph $H$ and a positive integer $n$, a Picker-Chooser $H$-game is a biased game played on the edge set of $K_n$ in which Picker is trying to force many copies of $H$ and Chooser is trying to prevent him from doing so. In this paper we conjecture that the value of the game is roughly the same as the expected number of copies of $H$ in the random graph $G(n,p)$ and prove our conjecture for special cases of $H$ such as complete graphs and trees.
For a graph $G$ the random $n$-lift of $G$ is obtained by replacing each of its vertices by a set of $n$ vertices, and joining a pair of sets by a random matching whenever the corresponding vertices of $G$ are adjacent. We show that asymptotically almost surely the random lift of a graph $G$ is hamiltonian, provided $G$ has the minimum degree at least $5$ and contains two disjoint Hamiltonian cycles whose union is not a bipartite graph.
Bootstrap percolation on the random graph $G_{n,p}$ is a process of spread of "activation" on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least $r\geq2$ active neighbors become active as well. We study the size $A^*$ of the final active set. The parameters of the model are, besides $r$ (fixed) and $n$ (tending to $\infty$), the size $a=a(n)$ of the initially active set and the probability $p=p(n)$ of the edges in the graph. We show that the model exhibits a sharp phase transition: depending on the parameters of the model, the final size of activation with a high probability is either $n-o(n)$ or it is $o(n)$. We provide a complete description of the phase diagram on the space of the parameters of the model. In particular, we find the phase transition and compute the asymptotics (in probability) for $A^*$; we also prove a central limit theorem for $A^*$ in some ranges. Furthermore, we provide the asymptotics for the number of steps until the process stops.
The Vapnik-Červonenkis dimension is a complexity measure of set-systems, or hypergraphs. Its application to graphs is usually done by considering the sets of neighborhoods of the vertices (cf. Alon et al. (2006) and Chepoi, Estellon, and Vaxes (2007)), hence providing a set-system. But the graph structure is lost in the process. The aim of this paper is to introduce the notion of paired VC-dimension, a generalization of VC-dimension to set-systems endowed with a graph structure, hence a collection of pairs of subsets. The classical VC-theory is generally used in combinatorics to bound the transversality of a hypergraph in terms of its fractional transversality and its VC-dimension. Similarly, we bound the chromatic number in terms of fractional transversality and paired VC-dimension. This approach turns out to be very useful for a class of problems raised by Erdős and Simonovits (1973) asking for H-free graphs with minimum degree at least cn and arbitrarily high chromatic number, where H is a fixed graph and c a positive constant. We show how the usual VC-dimension gives a short proof of the fact that triangle-free graphs with minimum degree at least n/3 have bounded chromatic number, where $n$ is the number of vertices. Using paired VC-dimension, we prove that if the chromatic number of $H$-free graphs with minimum degree at least cn is unbounded for some positive c, then it is unbounded for all c<1/3. In other words, one can find H-free graphs with unbounded chromatic number and minimum degree arbitrarily close to n/3. These H-free graphs are derived from a construction of Hajnal. The large chromatic number follows from the Borsuk-Ulam Theorem.
For a graph $L$ and an integer $k\geq 2$, $R_k(L)$ denotes the smallest integer $N$ for which for any edge-colouring of the complete graph $K_N$ by $k$ colours there exists a colour $i$ for which the corresponding colour class contains $L$ as a subgraph. Bondy and Erdős conjectured that for an odd cycle $C_n$ on $n$ vertices, $$R_k(C_n) = 2^{k-1}(n-1)+1 \text{for $n>3$.}$$ They proved the case when $k=2$ and also provided an upper bound $R_k(C_n)\leq (k+2)!n$. Recently, this conjecture has been verified for $k=3$ if $n$ is large. In this note, we prove that for every integer $k\geq 4$, $$R_k(C_n)\leq k2^kn+o(n), \text{as $n\to\infty$.}$$ When $n$ is even, Yongqi, Yuansheng, Feng, and Bingxi gave a construction, showing that $R_k(C_n)\geq (k-1)n-2k+4.$ Here we prove that if $n$ is even, then $$R_k(C_n)\leq kn+o(n), \text{as $n\to\infty$.}$$
Let $P(n,M)$ be a graph chosen uniformly at random from the family of all labeled planar graphs with $n$ vertices and $M$ edges. In the paper we study the component structure of $P(n,M)$. Combining counting arguments with analytic techniques, we show that there are two critical periods in the evolution of $P(n,M)$. The first one, of width $Θ(n^{2/3})$, is analogous to the phase transition observed in the standard random graph models and takes place for $M=n/2+O(n^{2/3})$, when the largest complex component is formed. Then, for $M=n+O(n^{3/5})$, when the complex components cover nearly all vertices, the second critical period of width $n^{3/5}$ occurs. Starting from that moment increasing of $M$ mostly affects the density of the complex components, not its size.
For a sequence p=(p(1),p(2), ...) let G(n,p) denote the random graph with vertex set {1,2, ...,n} in which two vertices i, j are adjacent with probability p(|i-j|), independently for each pair. We study how the convergence of probabilities of first order properties of G(n,p), can be affected by the behaviour of p and the strength of the language we use.