Arithmetic progressions of length three in subsets

We solve a problem of Krivelevich, Kwan and Sudakov concerning the threshold for containment all bounded degree spanning trees in model randomly perturbed dense graphs. More precisely, we show that, if start with graph G α on n vertices δ ( ) ≥ αn > 0 add to it binomial random , C / ), then high probability ∪ contains copies maximum at most Δ simultaneously, where depends only Δ.

For a graph H and an integer r ≥ 2, the induced r-size-Ramsey number of is defined to be smallest m for which there exists G with edges following property: however one colours colours, always monochromatic subgraph ′ that isomorphic . This concept closely related classical -size-Ramsey Erdős, Faudree, Rousseau Schelp, -induced Ramsey number, natural notion appears in problems conjectures due to, among others, Graham Rödl, Trotter. Here, we prove result implies cycle C ℓ at most c some...

Mauduit and Sárközy introduced studied certain numerical parameters associated to finite binary sequences EN ∈ {−1, 1}N in order measure their 'level of randomness'. Those parameters, the normality N(EN), well-distribution W(EN), correlation Ck(EN) k, focus on different combinatorial aspects EN. In work, amongst others, (i) investigated relationship among those minimal possible value, (ii) estimated W(EN) for explicitly constructed suggested have a 'pseudorandom nature', (iii) value...

In 1983, Chvátal, Trotter and the two senior authors proved that for any Δ there exists a constant B such that, n, 2-colouring of edges complete graph KN with N⩾Bn vertices yields monochromatic copy H has n maximum degree Δ. We prove may be replaced by sparser G N O(N2−1/Δlog1/ΔN) edges, N=⌈B′n⌉ some B′ depends only on Consequently, so-called size-Ramsey number is O(n2−1/Δlog1/Δn). Our approach based random graphs; in fact, we show classical Erdős–Rényi numerical parameters above satisfies...

Abstract A set of non‐negative integers is called a Sidon if all the sums , with and 1 are distinct. well‐known problem on sets determination maximum possible size F ( n ) subset . Results Chowla, Erdős, Singer Turán from 1940s give that We study subsets sparse random integers, replacing ‘dense environment’ by sparse, R ask how large can be, we require S should be set. Let cardinality equiprobable. investigate variable where taken over obtain quite precise information for whole range m as...

The blow-up lemma states that a system of super-regular pairs contains all bounded degree spanning graphs as subgraphs embed into corresponding complete pairs. This has far-reaching applications in extremal combinatorics. We prove sparse analogues the for random and pseudorandom graphs. Our main results are following three versions lemma: one embedding with maximum $Δ$ $G(n,p)$ $p=C(\log n/n)^{1/Δ}$; degeneracy $D$ $p=C_Δ\big(\log n/n\big)^{1/(2D+1)}$; $(p,cp^{\max(4,(3Δ+1)/2)}n)$-bijumbled...

The celebrated Erdős–Ko–Rado theorem determines the maximum size of a $k$-uniform intersecting family. Hilton–Milner family that is not subfamily so-called In turn, it natural to ask what an neither nor is. For $k\ge 4$, this was solved (implicitly) in same paper by 1967. We give different and simpler proof, based on shifting method, which allows us solve all cases 3$ characterize extremal families achieving value.

Abstract be a random Q n ”‐process, that is let 0 the empty spanning subgraph of cube and, for 1 ⩽ t M = nN /2 2 −1 , graph obtained from t−1 by addition an edge not present in . When about N /2, typical undergoes certain “phase transition'': component structure changes sudden and surprising way. Let (1 + ϵ) where ϵ independent Then all components have o(N) vertices if < 0, while > then, as proved Ajtai, Komlós, Szemerédi, has “giant” with at least α(ϵ) vertices, 0. In this note we...

Abstract Let G be a graph on n vertices with maximum degree Δ. We use the Lovász local lemma to show following two results about colourings χ of edges complete K . If for each vertex v colouring assigns colour at most ( ‐ 2)/(22.4Δ 2 ) emanating from , then there is copy in which properly edge‐coloured by χ. This improves result Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409–433, 2003]. On other hand, if /(51Δ such that edge receives different proves conjecture...

For k ≥ 2 and r 1 such that + 4, we prove that, for any α > 0, there exists ε 0 the union of an n ‐vertex ‐graph with minimum codegree a binomial random on same vertex set contains th power tight Hamilton cycle high probability. This result = was first proved by McDowell Mycroft.

In this paper we determine the local and global resilience of random graphs $G_{n, p}$ ($p \gg n^{-1}$) with respect to property containing a cycle length at least $(1-\alpha)n$. Roughly speaking, given $\alpha > 0$, smallest $r_g(G, \alpha)$ that almost surely every subgraph $G = G_{n, having more than \alpha) |E(G)|$ edges contains $(1 - n$ (global resilience). We also obtain, for < 1/2$, $r_l(G, such any $H \subseteq G$ $\deg_H(v)$ larger \deg_G(v)$ all $v \in V(G)$ (local The...

Let Δ ≥ 2 be a fixed integer. We show that the random graph ${\mathcal{G}_{n,p}}$ with $p\gg (\log n/n)^{1/\Delta}$ is robust respect to containment of almost spanning bipartite graphs H maximum degree and sublinear bandwidth in following sense: asymptotically surely, if an adversary deletes arbitrary edges from such way each vertex loses less than half its neighbours, then resulting still contains copy all .