For given posets $P$ and $Q$ and an integer $n$, the generalized Turán problem for posets asks for the maximum number of copies of $Q$ in a $P$-free subset of the $n$-dimensional Boolean lattice, $2^{[n]}$. In this paper, among other results, we show the following: (i) For every $n\geq 5$, the maximum number of 2-chains in a butterfly-free subfamily of $2^{[n]}$ is $\lceil\frac{n}{2} \rceil\binom{n}{\lfloor n/2\rfloor}$. (ii) For every fixed $s$, $t$ and $k$, a $K_{s,t}$-free family in $2^{[n]}$ has $O (n\binom{n}{\lfloor n/2\rfloor})$ $k$-chains. (iii) For every $n\geq 3$, the maximum number of $2$-chains in an ${N}$-free family is $\binom{n}{\lfloor n/2\rfloor}$, where ${N}$ is a poset on 4 distinct elements $\{p_1,p_2,q_1,q_2\}$ for which $p_1 < q_1$, $p_2 < q_1$ and $p_2 < q_2$. (iv) We also prove exact results for the maximum number of 2-chains in a family that has no 5-path and asymptotic estimates for the number of 2-chains in a family with no 6-path.

The Hall ratio of a graph $G$ is the maximum value of $v(H) / \alpha(H)$ taken over all non-null subgraphs $H \subseteq G$. For any graph, the Hall ratio is a lower-bound on its fractional chromatic number. In this note, we present various constructions of graphs whose fractional chromatic number grows much faster than their Hall ratio. This refutes a conjecture of Harris.

Let ${\rm ex}_{\mathcal{P}}(n,T,H)$ denote the maximum number of copies of $T$ in an $n$-vertex planar graph which does not contain $H$ as a subgraph. When $T=K_2$, ${\rm ex}_{\mathcal{P}}(n,T,H)$ is the well-studied function, the planar Turán number of $H$, denoted by ${\rm ex}_{\mathcal{P}}(n,H)$. The topic of extremal planar graphs was initiated by Dowden [ J. Graph Theory, 83 (2016), pp. 213--230]. He obtained a sharp upper bound for both ${\rm ex}_{\mathcal{P}}(n,C_4)$ and ${\rm ex}_{\mathcal{P}}(n,C_5)$. Later on, Lan, Shi, and Song continued this topic and proved that ${\rm ex}_{\mathcal{P}}(n,C_6)\leq \frac{18(n-2)}{7}$. In this paper, we give a sharp upper bound ${\rm ex}_{\mathcal{P}}(n,C_6) \leq \frac{5}{2}n-7$, for all $n\geq 18$, which improves Lan, Shi, and Song's result. We also pose a conjecture on ${\rm ex}_{\mathcal{P}}(n,C_k)$, for $k\geq 7$.

A graphic sequence $\pi$ is potentially $H$-graphic if there is some realization of $\pi$ that contains $H$ as a subgraph. The Erdös--Jacobson--Lehel problem asks one to determine $\sigma(H,n)$, the minimum even integer such that any $n$-term graphic sequence $\pi$ with sum at least $\sigma(H,n)$ is potentially $H$-graphic. The parameter $\sigma(H,n)$ is known as the potential function of $H$, and can be viewed as a degree sequence variant of the classical extremal function ${ex}(n,H)$. Recently, Ferrara et al. [ Combinatorica 36 (2016), pp. 687--702] determined $\sigma(H,n)$ asymptotically for all $H$, which is analogous to the Erdös--Stone--Simonovits theorem that determines ${ex}(n,H)$ asymptotically for nonbipartite $H$. In this paper, we investigate a stability concept for the potential number, inspired by Simonovits' classical result on the stability of the extremal function. We first define a notion of stability for the potential number that is a natural analogue to the stability given by Simonovits. However, under this definition, many families of graphs are not $\sigma$-stable, establishing a stark contrast between the extremal and potential functions. We then give a sufficient condition for a graph $H$ to be stable with respect to the potential function, and characterize the stability of those graphs $H$ that contain an induced subgraph of order $\alpha(H)+1$ with exactly one edge.

In this paper we prove an asymptotic multipartite version of a well-known theorem of Kühn and Osthus by establishing, for any graph $H$ with chromatic number $r$, the asymptotic multipartite minimum degree threshold which ensures that a large $r$-partite graph $G$ admits a perfect $H$-tiling. We also give the threshold for an $H$-tiling covering all but a linear number of vertices of $G$, in a multipartite analogue of results of Komlós and of Shokoufandeh and Zhao.

In the Avoider-Enforcer game on the complete graph $K_n$, the players (Avoider and Enforcer) each take an edge in turn. Given a graph property $\mathcal{P}$, Enforcer wins the game if Avoider's graph has the property $\mathcal{P}$. An important parameter is $\tau_E(\mathcal{P})$, the smallest integer t such that Enforcer can win the game against any opponent in t rounds. In this paper, let $\mathcal{F}$ be an arbitrary family of graphs and $\mathcal{P}$ be the property that a member of $\mathcal{F}$ is a subgraph or is an induced subgraph. We determine the asymptotic value of $\tau_E(\mathcal{P})$ when $\mathcal{F}$ contains no bipartite graph and establish that $\tau_E(\mathcal{P})=o(n^2)$ if $\mathcal{F}$ contains a bipartite graph. The proof uses the game of JumbleG and the Szemerédi regularity lemma.

The strong chromatic number, $\chi_S(G)$, of an n‐vertex graph G is the smallest number k such that after adding $k\lceil n/k\rceil - n$ isolated vertices to G and considering any partition of the vertices of the resulting graph into disjoint subsets $V_1, \ldots, V_{\lceil n/k\rceil}$ of size k each, one can find a proper k‐vertex‐coloring of the graph such that each part $V_i$, $i=1, \ldots, \lceil n/k\rceil$, contains exactly one vertex of each color. For any graph G with maximum degree Δ, it is easy to see that $\chi_S(G) \geq \Delta + 1$. Recently, Haxell proved that $\chi_S(G) \leq 3\Delta - 1$. In this paper, we improve this bound for graphs with large maximum degree. We show that $\chi_S(G) \leq 2\Delta$ if $\Delta \geq n/6$ and prove that this bound is sharp.

In this paper we deal with codes identifying sets of vertices in random graphs, that is l-identifying codes. These codes enable us to detect sets of faulty processors in a multiprocessor system, assuming that the maximum number of faulty processors is bounded by a fixed constant l. The l-identifying codes or simply identifying codes are of special interest. For random graphs we use the model G(n,p), in which each one of the (/sub 2//sup n/) possible edges exists with probability p. We give upper and lower bounds on the minimum cardinality of an l-identifying code in a random graph, as well as threshold functions for the property of admitting such a code. We derive existence results from probabilistic constructions. A connection between identifying codes and superimposed codes is also established.