We improve the upper bound for the maximum possible number of stable matchings among$n$jobs and$n$applicants from 131072n+ O(1) to 3.55n+ O(1). To establish this bound, we state a novel formulation of a certain entropy bound that is easy to apply and may be of independent interest in counting other combinatorial objects.

Let $\mathcal{H}$ be an $r$-uniform hypergraph. The minimum positive co-degree of $\mathcal{H}$, denoted by $\delta_{r-1}^+(\mathcal{H})$, is the minimum $k$ such that if $S$ is an $(r-1)$-set contained in a hyperedge of $\mathcal{H}$, then $S$ is contained in at least $k$ hyperedges of $\mathcal{H}$. For $r\geq k$ fixed and $n$ sufficiently large, we determine the maximum possible size of an intersecting $r$-uniform $n$-vertex hypergraph with minimum positive co-degree $\delta_{r-1}^+(\mathcal{H}) \geq k$ and characterize the unique hypergraph attaining this maximum. This generalizes the Erd\Hos--Ko--Rado theorem which corresponds to the case $k=1$. Our proof is based on the delta-system method.

Let $L$ be a set of positive integers. We call a (directed) graph $G$ an $L$ -cycle graph if all cycle lengths in $G$ belong to $L$. Let $c(L,n)$ be the maximum number of cycles possible in an $n$-vertex $L$-cycle graph (we use $\vec{c}(L,n)$ for the number of cycles in directed graphs). In the undirected case we show that for any fixed set $L$, we have $c(L,n)=\Theta(n^{\lfloor k/\ell \rfloor})$, where $k$ is the largest element of $L$ and $2\ell$ is the smallest even element of $L$ (if $L$ contains only odd elements, then $c(L,n)=\Theta(n)$ holds). We also give a characterization of $L$-cycle graphs when $L$ is a single element. In the directed case we prove that for any fixed set $L$, we have $\vec{c}(L,n)=(1+o(1))(\frac{n-1}{k-1})^{k-1}$, where $k$ is the largest element of $L$. We determine the exact value of $\vec{c}(\{k\},n)$ for every $k$ and characterize all graphs attaining this maximum.

Let $E(G)$ and $V(G)$ denote the edge set and vertex set of a (hyper)graph $G$. Let $G$ be a graph and $\mathcal{H}$ be a hypergraph. We say that a hypergraph $\mathcal{H}$ is a Berge-$G$ if there is a bijection $f : E(G) \rightarrow E(\mathcal{H})$ such that for each $e \in E(G)$ we have $e \subset f(e)$. This generalizes the established definitions of “Berge path” and “Berge cycle” to general graphs. For a fixed graph $G$ we examine the maximum possible size of a hypergraph with no Berge-$G$ as a subhypergraph. In the present paper we prove general bounds for this maximum when $G$ is an arbitrary graph. We also consider the specific case when $G$ is a complete bipartite graph and prove an analogue of the Kövári--Sós--Turán theorem. In case $G$ is $C_4$, we improve the bounds given by Györi and Lemons [ Discrete Math., 312, (2012), pp. 1518--1520].

The Gyárfás tree packing conjecture states that any set of $n-1$ trees $T_{1},T_{2},\dots, T_{n-1}$ such that $T_i$ has $n-i+1$ vertices packs into $K_n$ (for $n$ large enough). We show that $t=\frac{1}{10}n^{1/4}$ trees $T_1,T_2,\dots, T_t$ such that $T_i$ has $n-i+1$ vertices packs into $K_{n+1}$ (for $n$ large enough). We also prove that any set of $t=\frac{1}{10}n^{1/4}$ trees $T_1,T_2,\dots, T_t$ such that no tree is a star and $T_i$ has $n-i+1$ vertices packs into $K_{n}$ (for $n$ large enough). Finally, we prove that $t=\frac{1}{4}n^{1/3}$ trees $T_1,T_2,\dots, T_t$ such that $T_i$ has $n-i+1$ vertices packs into $K_n$ as long as each tree has maximum degree at least $2n^{2/3}$ (for $n$ large enough). One of the main tools used in the paper is the famous spanning tree embedding theorem of Komlós, Sárközy, and Szemerédi [Combin. Probab. Comput., 10 (2001), pp. 397--416].

Let us write ${\mathcal D}_{{\mathcal F}}(G)=\{F \in {\mathcal F}:F\cap G=\emptyset\}$ for a set $G$ and a family ${\mathcal F}$. Then a family ${\mathcal F}$ of sets is said to be ($\le l$)-almost intersecting ($l$-almost intersecting) if for any $F \in {\mathcal F}$ we have $|{\mathcal D}_{{\mathcal F}}(F)| \le l$ ($|{\mathcal D}_{{\mathcal F}}(F)|= l$). In this paper we investigate the problem of finding the maximum size of an ($\le l$)-almost intersecting ($l$-almost intersecting) family ${\mathcal F}$.