We give a distributed algorithm which given ε > 0 finds a (1-ε)-factor approximation of a maximum f-matching in graphs G = (V,E) of sub-logarithmic expansion. Using a similar approach we also give a distributed approximation of a maximum b-matching in the same class of graphs provided the function b: V → ℤ^+ is L-Lipschitz for some constant L. Both algorithms run in O(log^* n) rounds in the LOCAL model, which is optimal.

Let $C^t$ denote the loose cycle on $t = 2s$ vertices, that is, the 3-uniform hypergraph obtained from a graph cycle $C$ on $s$ vertices by replacing each edge $e = \{u, v\}$ of $C$ with the edge triple $\{u, x_e, v\}$, where $x_e$ is uniquely assigned to $e$. We will give a tight minimum degree condition that guarantees all sufficiently large 3-uniform hypergraphs on $n\in t\mathbb{Z}$ vertices contain $\frac{n}{t}$ vertex disjoint copies of $C^t$.

In this paper we will give two distributed approximation algorithms (in the Local model) for the minimum dominating set problem. First we will give a distributed algorithm which finds a dominating set D of size O(gamma(G)) in a graph G which has no topological copy of K_h. The algorithm runs L_h rounds where L_h is a constant which depends on h only. This procedure can be used to obtain a distributed algorithm which given epsilon>0 finds in a graph G with no K_h-minor a dominating set D of size at most (1+epsilon)gamma(G). The second algorithm runs in O(log^*{|V(G)|}) rounds.

In 2006, Kühn and Osthus [J. Combin. Theory Ser. B, 96 (2006), pp. 767--821] showed that if a 3-graph $H$ on $n$ vertices has minimum codegree at least $(1/4 +o(1))n$ and $n$ is even, then $H$ has a loose Hamilton cycle. In this paper, we prove that the minimum codegree of $n/4$ suffices. The result is tight.

Bipartite graph tiling was studied by Zhao [SIAM J. Discrete Math., 23 (2009), pp. 888–900], who gave the best possible minimum degree conditions for a balanced bipartite graph on $2ms$ vertices to contain m vertex disjoint copies of $K_{s,s}$. Let $s 2s+1$. We give the best possible minimum degree condition in this case.

Let G and H be balanced $U,V$-bigraphs on $2n$ vertices with $\Delta(H)\leq2$. Let k be the number of components of H, $\delta_U:=\min\{\deg_G(u):u\in U\}$ and $\delta_V:=\min\{\deg_G(v):v\in V\}$. We prove that if n is sufficiently large and $\delta_U+\delta_V\geq n+k$, then G contains H. This answers a question of Amar in the case that n is large. We also show that G contains H even when $\delta_U+\delta_V\geq n+2$ as long as n is sufficiently large in terms of k and $\delta(G)\geq\frac{n}{200k}+1$.

We give an efficient distributed algorithm that finds an almost optimal packing of a graph H in a planar graph G. The algorithm is deterministic and its running time is poly-logarithmic in the order of G.

The pebbling number of a graph is the smallest number t such that from any initial configuration of t pebbles one can move a pebble to any prescribed vertex by a sequence of pebbling steps. It is known that graphs whose connectivity is high compared to their diameter have a pebbling number as small as possible. We will use the above result to prove two related theorems. First, answering a question of the second author, we show that there exist graphs of arbitrarily high constant girth and least possible pebbling number. In the second application, we prove that the product of two graphs of high minimum degree has a pebbling number equal to the number of vertices of the product. This shows that Graham's product conjecture is true in the case of high minimum degree graphs. In addition, we consider a probabilistic variant of the pebbling problem and establish a pebbling threshold result for products of paths. The last result shows that the sequence of paths satisfies the probabilistic analogue of Graham's product conjecture.

In this paper, we will consider the problem of designing an efficient algorithm that finds an $\epsilon$-regular partition of an l-uniform hypergraph.

A constructive lower bound on the quasi-Ramsey numbers and the tournament ranking function was obtained in [S. Poljak, V. Rödl, and J. Spencer, SIAM J. Discrete Math., (1) 1988, pp. 372--376]. We consider the weighted versions of both problems. Our method yields a polynomial time heuristic with guaranteed lower bound for the linear ordering problem.