We prove that every connected graph of order n ≥ 2 has an induced subgraph with all degrees odd of order at least cn/log n, where cis a constant. We also give a bound in terms of chromatic number, and resolve the analogous problem for random graphs.

We investigate the asymptotic behaviour of the average displacement of the simple random walk on the Sierpiński graph. The existence of an oscillating factor in this asymptotics is shown rigorously. The proof depends mainly on the analysis of the corresponding generating function. Using a functional equation and techniques from complex analysis we obtain the desired properties of this generating function.

We study the number of edge-disjoint Hamilton cycles one can guarantee in a sufficiently large graph G on n vertices with minimum degree δ=(1/2+α)n. For any constant α>0, we give an optimal answer in the following sense: let regeven(n,δ) denote the degree of the largest even-regular spanning subgraph one can guarantee in a graph on n vertices with minimum degree δ. Then the number of edge-disjoint Hamilton cycles we find equals regeven(n,δ)/2. The value of regeven(n,δ) is known for infinitely many values of n and δ. We also extend our results to graphs G of minimum degree δ ≥ n/2, unless G is close to the extremal constructions for Dirac's theorem. Our proof relies on a recent and very general result of Kühn and Osthus on Hamilton decomposition of robustly expanding regular graphs.

The notion of tree entropy was introduced by the author as a normalized limit of the number of spanning trees in finite graphs, but is defined on random infinite rooted graphs. We give some new expressions for tree entropy; one uses Fuglede–Kadison determinants, while another uses effective resistance. We use the latter to prove that tree entropy respects stochastic domination. We also prove that tree entropy is non-negative in the unweighted case, a special case of which establishes Lück's Determinant Conjecture for Cayley-graph Laplacians. We use techniques from the theory of operators affiliated to von Neumann algebras.

Let $G$ be a cyclic group of order $n$ and let $\mu = \{x_1,x_2, \dots, x_m\}$ be a sequence of elements of $G$. Let $k$ be the number of distinct values taken by the sequence $\mu$. Let $n\wedge \mu$ be the set of the $n$-subsequence sums.

We show that one of the following conditions holds:

1. $\mu$ has a value repeated $n-k+3$ times

2. $n\wedge \mu$ contains a non-null subgroup

3. $|n\wedge \mu|\geq m-n+k-2.$

We conjecture that the last condition could be improved to $|n\wedge \mu|\geq m-n+k-1$. This conjecture generalizes several known results. We also obtain a generalization of a recent result due to Bollobás and Leader.

We provide an estimate, sharp up to poly-logarithmic factors, of the asymptotic almost sure mixing time of the graph created by long-range percolation on the cycle of length N (). While it is known that the asymptotic almost sure diameter drops from linear to poly-logarithmic as the exponent s decreases below 2 [4, 9], the asymptotic almost sure mixing time drops from N2 only to Ns-1 (up to poly-logarithmic factors).

We consider a variant of the game of Cops and Robbers, called Lazy Cops and Robbers, where at most one cop can move in any round. We investigate the analogue of the cop number for this game, which we call the lazy cop number. Lazy Cops and Robbers was recently introduced by Offner and Ojakian, who provided asymptotic upper and lower bounds on the lazy cop number of the hypercube. By coupling the probabilistic method with a potential function argument, we improve on the existing lower bounds for the lazy cop number of hypercubes.

For an integer $s\ges 2$, a property $\P^{(s)}$ is an infinite class of s-uniform hypergraphs closed under isomorphism. We say that a property $\P^{(s)}$ is \emph{hereditary\/} if~$\P^{(s)}$ is closed under taking induced subhypergraphs. Thus, for some `forbidden class' $\FF=\{\F_i^{(s)}\:i\in I\}$ of s-uniform hypergraphs, $\P^{(s)}$ is the set of all s-uniform hypergraphs not containing any $\F_i^{(s)}\in\FF$ as an induced subhypergraph. Let $\P^{(s)}_n$ be those hypergraphs of $\P^{(s)}$ on some fixed n-vertex set. For a set of s-uniform hypergraphs $\FF=\{\F_i^{(s)}\:i\in I\}$, let

\[ \exind(n,\FF)=\max\bigl|[n]^s{\setminus}(\M\cup\N)\vphantom{\big|}\bigr|, \]

where the maximum is taken over all $\M$ and $\N\subseteq[n]^s$ with $\M\cap\N=\emptyset$ such that, for all $\G\subseteq[n]^s{\setminus}(\M\cup\N)$, no $\F_i^{(s)}\in\FF$ appears as an induced subhypergraph of $\G\cup\M$. We show that

\[ \log_2\big|\P^{(3)}_n\big|=\exind(n,\FF)+o(n^3) \]

holds for $s=3$ and any hereditary property $\P^{(3)}$, where $\FF$ is a forbidden class associated with $\P^{(3)}$. This result complements a collection of analogous theorems already proved for graphs (i.e., $s=2$).

This is a continuation of our work on quasi-random graph properties. The class of quasi-random graphs is defined by certain equivalent graph properties possessed by random graphs. One of the most important of these properties is that, for fixed $\nu$, every fixed sample graph $L_\nu$ has the same frequency in $G_n$ as in the $p$-random graph. (This holds for both induced and not necessarily induced containment.) In [9] we proved that, if the frequency of just one fixed $L_\nu$ – as a not necessarily induced subgraph – in every ‘large’ induced subgraph $F_h\subseteq G_n$ is the same as for the random graphs, then $(G_n)$ is quasi-random. Here we shall investigate the analogous problem for induced subgraphs $L_\nu$. In such cases $(G_n)$ is not necessarily quasi-random.

We shall prove, among other things, that, for every regular sample graph $L_\nu$, $\nu\geqslant 4$, if the number of induced copies of $L_\nu$ in every induced $F_h\subseteq G_n$ is asymptotically the same as in a $p$-random graph (up to an error term $o(n^\nu)$), then $(G_n)$ is the union of (at most) two quasi-random graph sequences, with possibly distinct attached probabilities (assuming that $p\in (0,1)$, $e(L_\nu)>0$, and $L_\nu\ne K_\nu$).

We conjecture the same conclusion for every $L_\nu$ with $\nu\ge 4$, i.e., even if we drop the assumption of regularity.

We shall reduce the general problem to solving a system of polynomials. This gives a ‘simple’ algorithm to decide the problem for every given $L_\nu$.

Let S be a set of m clauses each containing three literals chosen at random in a set {p1, ¬p1,…,pn, ¬pn} of n propositional variables and their negations. Let be the set of all such S with m = cn for a fixed c > 0. We show, improving significantly over the first moment upper bound , that if m and n tend to infinity with , then almost all are unsatisfiable.

We provide sufficient conditions for packing two hypergraphs. The emphasis is on the asymptotic case when one of the hypergraphs has a bounded degree and the other is dense. As an application, we give an alternative proof for the bipartite case of the recently developed Blow-up Lemma [12].

This is a survey of a number of recent papers dealing with graphs from a geometric perspective. The main theme of these studies is the relationship between graph properties that are local in nature, and global graph parameters. Connections with the theory of distributed computing are pointed out and many open problems are presented.

This paper addresses the following question for a given graph H: What is the minimum number f(H) such that every graph with average degree at least f(H) contains H as a minor? Due to connections with Hadwiger's conjecture, this question has been studied in depth when H is a complete graph. Kostochka and Thomason independently proved that $f(K_t)=ct\sqrt{\ln t}$. More generally, Myers and Thomason determined f(H) when H has a super-linear number of edges. We focus on the case when H has a linear number of edges. Our main result, which complements the result of Myers and Thomason, states that if H has t vertices and average degree d at least some absolute constant, then $f(H)\leq 3.895\sqrt{\ln d}\,t$. Furthermore, motivated by the case when H has small average degree, we prove that if H has t vertices and q edges, then f(H) ⩽ t + 6.291q (where the coefficient of 1 in the t term is best possible).

A subgraph H in an edge-colouring is properly coloured if incident edges of H are assigned different colours, and H is rainbow if no two edges of H are assigned the same colour. We study properly coloured subgraphs and rainbow subgraphs forced in edge-colourings of complete graphs in which each vertex is incident to a large number of colours.

Given a set $L$ of $n$ lines in ${\mathbb R}^3$, joints are points in ${\mathbb R}^3$ that are incident to at least three non-coplanar lines in $L$. We show that there are at most $O(n^{5/3})$ incidences between $L$ and the set of its joints.

This result leads to related questions about incidences between $L$ and a set $P$ of $m$ points in ${\mathbb R}^3$. First, we associate with every point $p \in P$ the minimum number of planes it takes to cover all lines incident to $p$. Then the sum of these numbers is at most \[ O\big(m^{4/7}n^{5/7}+m+n\big).\] Second, if each line forms a fixed given non-zero angle with the $xy$-plane – we say the lines are equally inclined – then the number of (real) incidences is at most \[ O\big(\min\big\{m^{3/4}n^{1/2}\kappa(m),\ m^{4/7}n^{5/7}\big\} + m + n\big) , \] where $\kappa(m) \,{=}\, (\log m)^{O(\alpha^2(m))}$, and $\alpha(m)$ is the slowly growing inverse Ackermann function. These bounds are smaller than the tight Szemerédi–Trotter bound for point–line incidences in $\reals^2$, unless both bounds are linear. They are the first results of this type on incidences between points and $1$-dimensional objects in $\reals^3$. This research was stimulated by a question raised by G. Elekes.

The number of spanning trees in the giant component of the random graph (n, c/n) (c > 1) grows like exp{m(f(c)+o(1))} as n → ∞, where m is the number of vertices in the giant component. The function f is not known explicitly, but we show that it is strictly increasing and infinitely differentiable. Moreover, we give an explicit lower bound on f′(c). A key lemma is the following. Let PGW(λ) denote a Galton–Watson tree having Poisson offspring distribution with parameter λ. Suppose that λ*>λ>1. We show that PGW(λ*) conditioned to survive forever stochastically dominates PGW(λ) conditioned to survive forever.

A central result in extremal set theory is the celebrated theorem of Sperner from 1928, which gives the size of the largest family of subsets of [n] not containing a 2-chain, F1 ⊂ F2. Erdős extended this theorem to determine the largest family without a k-chain, F1 ⊂ F2 ⊂ . . . ⊂ Fk. Erdős and Katona, followed by Kleitman, asked how many chains must appear in families with sizes larger than the corresponding extremal bounds.

In 1966, Kleitman resolved this question for 2-chains, showing that the number of such chains is minimized by taking sets as close to the middle level as possible. Moreover, he conjectured the extremal families were the same for k-chains, for all k. In this paper, making the first progress on this problem, we verify Kleitman's conjecture for the families whose size is at most the size of the k + 1 middle levels. We also characterize all extremal configurations.

We study the lower tail large deviation problem for subgraph counts in a random graph. Let XH denote the number of copies of H in an Erdős–Rényi random graph $\mathcal{G}(n,p)$. We are interested in estimating the lower tail probability $\mathbb{P}(X_H \le (1-\delta) \mathbb{E} X_H)$ for fixed 0 < δ < 1.

Thanks to the results of Chatterjee, Dembo and Varadhan, this large deviation problem has been reduced to a natural variational problem over graphons, at least for p ≥ n−αH (and conjecturally for a larger range of p). We study this variational problem and provide a partial characterization of the so-called ‘replica symmetric’ phase. Informally, our main result says that for every H, and 0 < δ < δH for some δH > 0, as p → 0 slowly, the main contribution to the lower tail probability comes from Erdős–Rényi random graphs with a uniformly tilted edge density. On the other hand, this is false for non-bipartite H and δ close to 1.

A detachment of a hypergraph is formed by splitting each vertex into one or more subvertices, and sharing the incident edges arbitrarily among the subvertices. For a given edge-coloured hypergraph , we prove that there exists a detachment such that the degree of each vertex and the multiplicity of each edge in (and each colour class of ) are shared fairly among the subvertices in (and each colour class of , respectively).

Let be a hypergraph with vertex partition {V1,. . .,Vn}, |Vi| = pi for 1 ≤ i ≤ n such that there are λi edges of size hi incident with every hi vertices, at most one vertex from each part for 1 ≤ i ≤ m (so no edge is incident with more than one vertex of a part). We use our detachment theorem to show that the obvious necessary conditions for to be expressed as the union 1 ∪ ··· ∪ k of k edge-disjoint factors, where for 1 ≤ i ≤ k, i is ri-regular, are also sufficient. Baranyai solved the case of h1 = ··· = hm, λ1 = ··· = λm = 1, p1 = ··· = pm, r1 = ··· = rk. Berge and Johnson (and later Brouwer and Tijdeman, respectively) considered (and solved, respectively) the case of hi = i, 1 ≤ i ≤ m, p1 = ··· = pm = λ1 = ··· = λm = r1 = ··· = rk = 1. We also extend our result to the case where each i is almost regular.

This article presents uniform random generators of plane partitions according to size (the number of cubes in the 3D interpretation). Combining a bijection of Pak with the method of Boltzmann sampling, we obtain random samplers that are slightly superlinear: the complexity is O(n(ln n)3) in approximate-size sampling and O(n4/3) in exact-size sampling (under a real-arithmetic computation model). To our knowledge, these are the first polynomial-time samplers for plane partitions according to size (there exist polynomial-time samplers of another type, which draw plane partitions that fit inside a fixed bounding box). The same principles yield efficient samplers for (a × b)-boxed plane partitions (plane partitions with two dimensions bounded), and for skew plane partitions. The random samplers allow us to perform simulations and observe limit shapes and frozen boundaries, which have been analysed recently by Cerf and Kenyon for plane partitions, and by Okounkov and Reshetikhin for skew plane partitions.