We say that α ∈ [0, 1) is a jump for an integer r ≥ 2 if there exists c(α) > 0 such that for all ϵ > 0 and all t ≥ 1, any r-graph with n ≥ n0(α, ϵ, t) vertices and density at least α + ϵ contains a subgraph on t vertices of density at least α + c.

The Erdős–Stone–Simonovits theorem [4, 5] implies that for r = 2, every α ∈ [0, 1) is a jump. Erdős [3] showed that for all r ≥ 3, every α ∈ [0, r!/rr) is a jump. Moreover he made his famous ‘jumping constant conjecture’, that for all r ≥ 3, every α ∈ [0, 1) is a jump. Frankl and Rödl [7] disproved this conjecture by giving a sequence of values of non-jumps for all r ≥ 3.

We use Razborov's flag algebra method [9] to show that jumps exist for r = 3 in the interval [2/9, 1). These are the first examples of jumps for any r ≥ 3 in the interval [r!/rr, 1). To be precise, we show that for r = 3 every α ∈ [0.2299, 0.2316) is a jump.

We also give an improved upper bound for the Turán density of K4− = {123, 124, 134}: π(K4−) ≤ 0.2871. This in turn implies that for r = 3 every α ∈ [0.2871, 8/27) is a jump.

For an increasing monotone graph property the local resilience of a graph G with respect to is the minimal r for which there exists a subgraph H ⊆ G with all degrees at most r, such that the removal of the edges of H from G creates a graph that does not possess . This notion, which was implicitly studied for some ad hoc properties, was recently treated in a more systematic way in a paper by Sudakov and Vu. Most research conducted with respect to this distance notion focused on the binomial random graph model (n, p) and some families of pseudo-random graphs with respect to several graph properties, such as containing a perfect matching and being Hamiltonian, to name a few. In this paper we continue to explore the local resilience notion, but turn our attention to random and pseudo-random regular graphs of constant degree. We investigate the local resilience of the typical random d-regular graph with respect to edge and vertex connectivity, containing a perfect matching, and being Hamiltonian. In particular, we prove that for every positive ϵ and large enough values of d, with high probability, the local resilience of the random d-regular graph, n, d, with respect to being Hamiltonian, is at least (1−ϵ)d/6. We also prove that for the binomial random graph model (n, p), for every positive ϵ > 0 and large enough values of K, if p > then, with high probability, the local resilience of (n, p) with respect to being Hamiltonian is at least (1−ϵ)np/6. Finally, we apply similar techniques to positional games, and prove that if d is large enough then, with high probability, a typical random d-regular graph G is such that, in the unbiased Maker–Breaker game played on the edges of G, Maker has a winning strategy to create a Hamilton cycle.

Consider the barycentric subdivision which cuts a given triangle along its medians to produce six new triangles. Uniformly choosing one of them and iterating this procedure gives rise to a Markov chain. We show that, almost surely, the triangles forming this chain become flatter and flatter in the sense that their isoperimetric values go to infinity with time. Nevertheless, if the triangles are renormalized through a similitude to have their longest edge equal to [0, 1] ⊂ ℂ (with 0 also adjacent to the shortest edge), their aspect does not converge and we identify the limit set of the opposite vertex with the segment [0, 1/2]. In addition we prove that the largest angle converges to π in probability. Our approach is probabilistic, and these results are deduced from the investigation of a limit iterated random function Markov chain living on the segment [0, 1/2]. The stationary distribution of this limit chain is particularly important in our study.

We consider the following process for generating large random cubic graphs. Starting with a given graph, repeatedly add edges that join the midpoints of two randomly chosen edges. We show that the growing graph asymptotically almost surely has logarithmic diameter. This process is motivated by a particular type of peer-to-peer network. Our method extends to similar processes that generate regular graphs of higher degree.

Let A be a finite non-empty set of integers. An asymptotic estimate of the size of the sum of several dilates was obtained by Bukh. The unique known exact bound concerns the sum |A + k⋅A|, where k is a prime and |A| is large. In its full generality, this bound is due to Cilleruelo, Serra and the first author.

Let k be an odd prime and assume that |A| > 8kk. A corollary to our main result states that |2⋅A + k⋅A|≥(k+2)|A|−k2−k+2. Notice that |2⋅P+k⋅P|=(k+2)|P|−2k, if P is an arithmetic progression.

Let be a set of terms over an arbitrary (but finite) number of Boolean variables. Let U() be the set of truth assignments that satisfy exactly one term in . Motivated by questions in computational complexity, Rudich conjectured that there exist ∊, δ > 0 such that, if is any set of terms for which U() contains at least a (1−∊)-fraction of all truth assignments, then there exists a term t ∈ such that at least a δ-fraction of assignments satisfy some term of sharing a variable with t [8].

We prove a stronger version: for any independent assignment of the variables (not necessarily the uniform one), if the measure of U() is at least 1 − ∊, there exists a t ∈ such that the measure of the set of assignments satisfying either t or some term incompatible with t (i.e., having no satisfying assignments in common with t) is at least . (A key part of the proof is a correlation-like inequality on events in a finite product probability space that is in some sense dual to Reimer's inequality [11], a.k.a. the BKR inequality [5], or the van den Berg–Kesten conjecture [3].)

We introduce a polynomial invariant of graphs on surfaces, PG, generalizing the classical Tutte polynomial. Topological duality on surfaces gives rise to a natural duality result for PG, analogous to the duality for the Tutte polynomial of planar graphs. This property is important from the perspective of statistical mechanics, where the Tutte polynomial is known as the partition function of the Potts model. For ribbon graphs, PG specializes to the well-known Bollobás–Riordan polynomial, and in fact the two polynomials carry equivalent information in this context. Duality is also established for a multivariate version of the polynomial PG. We then consider a 2-variable version of the Jones polynomial for links in thickened surfaces, taking into account homological information on the surface. An analogue of Thistlethwaite's theorem is established for these generalized Jones and Tutte polynomials for virtual links.

Let Ωn be the nn-element set consisting of all functions that have {1, 2, 3, . . ., n} as both domain and codomain. Let T(f) be the order of f, i.e., the period of the sequence f, f(2), f(3), f(4) . . . of compositional iterates. A closely related number, B(f) = the product of the lengths of the cycles of f, has previously been used as an approximation for T. This paper proves that the average values of these two quantities are quite different. The expected value of T is where k0 is a complicated but explicitly defined constant that is approximately 3.36. The expected value of B is much larger:

We introduce two graph polynomials and discuss their properties. One is a polynomial of two variables whose investigation is motivated by the performance analysis of the Bethe approximation of the Ising partition function. The other is a polynomial of one variable that is obtained by the specialization of the first one. It is shown that these polynomials satisfy deletion–contraction relations and are new examples of the V-function, which was introduced by Tutte (Proc. Cambridge Philos. Soc.43, 1947, p. 26). For these polynomials, we discuss the interpretations of special values and then obtain the bound on the number of sub-coregraphs, i.e., spanning subgraphs with no vertices of degree one. It is proved that the polynomial of one variable is equal to the monomer–dimer partition function with weights parametrized by that variable. The properties of the coefficients and the possible region of zeros are also discussed for this polynomial.