We prove a minimum degree version of the Kruskal--Katona theorem for triple systems: given $d\ge 1/4$ and a triple system $\mathcal{F}$ on $n$ vertices with minimum degree $\delta(\mathcal{F})\ge d\binom n2$, we obtain asymptotically tight lower bounds for the size of its shadow. Equivalently, for $t\ge n/2-1$, we asymptotically determine the minimum size of a graph on $n$ vertices, in which every vertex is contained in at least $\binom t2$ triangles. This can be viewed as a variant of the Rademacher--Turán problem.

Let $r\ge 3$. Given an $r$-graph $H$, the minimum codegree $\delta_{r-1}(H)$ is the largest integer $t$ such that every $(r-1)$-subset of $V(H)$ is contained in at least $t$ edges of $H$. Given an $r$-graph $F$, the codegree Turán density $\gamma(F)$ is the smallest $\gamma >0$ such that every $r$-graph on $n$ vertices with $\delta_{r-1}(H)\ge (\gamma + o(1))n$ contains $F$ as a subhypergraph. Using results on the independence number of hypergraphs, we show that there are constants $c_1, c_2>0$ depending only on $r$ such that $1 - c_2 \tfrac{\ln t}{t^{r-1}} \le \gamma(K_t^r) \le 1 - c_1 \tfrac{\ln t}{t^{r-1}},$ where $K_t^r$ is the complete $r$-graph on $t$ vertices. This gives the best general bounds for $\gamma(K_t^r)$.

Given two 3-uniform hypergraphs $F$ and $G=(V,E)$, we say that $G$ has an $F$-covering if we can cover $V$ with copies of $F$. The minimum codegree of $G$ is the largest integer $d$ such that every pair of vertices from $V$ is contained in at least $d$ triples from $E$. Define $c_2(n,F)$ to be the largest minimum codegree among all $n$-vertex 3-graphs $G$ that contain no $F$-covering. Determining $c_2(n,F)$ is a natural problem intermediate (but distinct) from the well-studied Turán problems and tiling problems. In this paper, we determine $c_2(n, K_4)$ (for $n>98$) and the associated extremal configurations (for $n>998$), where $K_4$ denotes the complete 3-graph on 4 vertices. We also obtain bounds on $c_2(n,F)$ which are apart by at most 2 in the cases where $F$ is $K_4^ -$ ($K_4$ with one edge removed), $K_5^-$, and the tight cycle $C_5$ on 5 vertices.

Let $B_i^{(k)}$ be the $k$-uniform hypergraph whose vertex set is of the form $S\cup T$, where $|S|=i$, $|T|=k-1$, and $S\cap T=\emptyset$, and whose edges are the $k$-subsets of $S\cup T$ that contain either $S$ or $T$. We derive upper and lower bounds for the Turán density of $B_i^{(k)}$ that are close to each other as $k\to\infty$. We also obtain asymptotically tight bounds for the Turán density of several other infinite families of hypergraphs. The constructions that imply the lower bounds are derived from elementary number theory by probabilistic arguments, and the upper bounds follow from some results of de Caen, Sidorenko, and Keevash.

The complete area coverage problem in Wireless Sensor Networks (WSNs) has been extensively studied in the literature. However, many applications do not require complete coverage all the time. For such applications, one effective method to save energy and prolong network lifetime is to partially cover the area. This method for prolonging network lifetime recently attracts much attention. However, due to the hardness of verifying the coverage ratio, all the existing centralized or distributed but nonparallel algorithms for partial coverage have very high time complexities. In this work, we propose a framework which can transform almost any existing complete coverage algorithm to a partial coverage one with any coverage ratio by running a complete coverage algorithm to find full coverage sets with virtual radii and converting the coverage sets to partial coverage sets via adjusting sensing radii. Our framework can preserve the characteristics of the original algorithms and the conversion process has low time complexity. The framework also guarantees some degree of uniform partial coverage of the monitored area.

The complete area coverage problem in wireless sensor networks (WSNs) where every point inside an area is covered by an active sensor has been extensively studied in the literature. However, there are many applications that do not always require complete coverage. For such applications, an effective method to save energy and prolong network lifetime is to partially cover the area. However, due to the hardness to verify the ratio of the covered area over the entire monitored area (coverage ratio), all the existing algorithms for partial coverage have very high time complexities (either centralized algorithms or distributed but non-parallel algorithms). Besides, all the existing algorithms are intentionally designed for partial coverage, thus they do not utilize the various exiting methods for the complete coverage problem. In this work, we propose a framework that can convert almost any existing algorithm for complete coverage to a one for partial coverage with any coverage ratio. Our framework can preserve the characteristics of the original algorithms and the conversion process has low time complexity. The framework also guarantees some degree of uniform partial coverage of the monitored area.

We first answer a question of de Caen [Extremal Problems for Finite Sets, János Bolyai Math. Soc., Budapest, 1994, pp. 187–197]: given $r\geq3$, if G is an r-uniform hypergraph on n vertices such that every $r+1$ vertices span 1 or $r+1$ edges, then $G=K^r_n$ or $K^r_{n-1}$, assuming that $n>(p-1)r$, where p is the smallest prime factor of $r-1$. We then show that the Turán density $\pi(K^r_{r+1})\leq1-1/r-(1-1/r^{p-1})(r-1)^2/(2r^p({r+p\choose p-1}+{r+1\choose 2}))$, for all even $r\geq4$, improving a well-known bound $1-\frac{1}{r}$ of de Caen [Ars Combin., 16 (1983), pp. 5–10] and Sidorenko [Vestnik Moskov. Univ. Ser. I Mat. Mekh., 76 (1982), pp. 3–6].

For each $s\geq2$, there exists $m_0$ such that the following holds for all $m\geq m_0$: Let G be a bipartite graph with $n=ms$ vertices in each partition set. If m is odd and minimum degree $\delta(G)\geq\frac{n+3s}{2}-2$, then G contains m vertex-disjoint copies of $K_{s,s}$. If m is even, the same holds under the weaker condition $\delta(G)\geq n/2+s-1$. This is sharp and much stronger than a conjecture of Wang [Discrete Math., 187 (1998), pp. 221–231] (for large n).