For a graph whose edges are coloured blue or red, the -semi-inducibility problem asks for the maximum, over all graphs of given order , of the number of injections from the vertex set of into the vertex set of that send red (resp. blue) edges of to edges (resp. non-edges) of . We consider all possible 4-vertex non-complete graphs and essentially resolve all remaining cases except when is the 3-edge path coloured blue-blue-red in this order (or is equivalent to this case). Some of our proofs are computer-generated, using the flag algebra method of Razborov.

Abstract. For a positive real number [Formula: see text], the [Formula: see text]-norm [Formula: see text] of a graph [Formula: see text] is the sum of the [Formula: see text]th powers of all vertex degrees. We study the maximum [Formula: see text]-norm [Formula: see text] of [Formula: see text]-free graphs on [Formula: see text] vertices. Füredi and Kündgen [ J. Graph Theory, 51 (2006), pp. 37–48] showed that for every bipartite graph [Formula: see text], there exists a threshold [Formula: see text] such that for [Formula: see text], the order of [Formula: see text] is governed by pseudorandom constructions, while for [Formula: see text], it is governed by star-like constructions, assuming a mild assumption on the growth rate of [Formula: see text]. The main contribution of our paper is extending this result to hypergraphs. Moreover, in the case of graphs, our proof differs from that in [Z. Füredi and A. Kündgen, J. Graph Theory, 51 (2006), pp. 37–48], offering the advantage of producing the correct constant factor when [Formula: see text]. When [Formula: see text], Füredi and Kündgen proved a general upper bound on [Formula: see text] that is tight up to a [Formula: see text] factor and conjectured that this factor is unnecessary. We confirm this conjecture for several well-studied bipartite graphs, including one-sided degree-bounded graphs that meet Füredi’s bound and families of short even cycles.

We prove that the density of any covering singleinsertion codeC⊆Xrover then-symbol alphabet X cannot be smaller than 1/r+ δrfor some positive real δrnot depending onn. This improves the volume lower bound of 1=(r+ 1). On the other hand, we observe that, for all sufficiently larger, ifntends to infinity then the asymptotic upper bound of 7=(r+ 1) due to Lenz et al. (2021) can be improved to 4.911=(r+ 1). Both the lower and the upper bounds are achieved by relating the code density to the Turán density from extremal combinatorics. For the last task, we use the analytic framework of measurable subsets of the real cube [0; 1]r.

Given a family of 3-graphs $\mathcal{F}$, we define its codegree threshold $\mathrm{coex}(n, \mathcal{F})$ to be the largest number $d=d(n)$ such that there exists an $n$-vertex 3-graph in which every pair of vertices is contained in at least $d$ 3-edges but which contains no member of $\mathcal{F}$ as a subgraph. Let $F_{3,2}$ be the 3-graph on $\{a,b,c,d,e\}$ with 3-edges $abc$, $abd$, $abe$, and $cde$. In this paper, we give two proofs that $\mathrm{coex}(n, \{F_{3,2}\})= \big(\frac{1}{3}+o(1)\big)n,$ the first by a direct combinatorial argument and the second via a flag algebra computation. Information extracted from the latter proof is then used to obtain a stability result, from which in turn we derive the exact codegree threshold for all sufficiently large $n$: $\mathrm{coex}(n, \{F_{3,2}\})= \lfloor n/3 \rfloor-1$ if $n$ is congruent to $1$ modulo $3$, and $\lfloor n/3 \rfloor$ otherwise. In addition we determine the set of codegree-extremal configurations for all sufficiently large $n$.

This paper extends the scenario of the Four Color Theorem in the following way. Let [Formula: see text] be the set of all [Formula: see text]-uniform hypergraphs that can be (linearly) embedded into [Formula: see text]. We investigate lower and upper bounds on the maximum (weak) chromatic number of hypergraphs in [Formula: see text]. For example, we can prove that for [Formula: see text] there are hypergraphs in [Formula: see text] on [Formula: see text] vertices whose chromatic number is [Formula: see text], whereas the chromatic number for [Formula: see text]-vertex hypergraphs in [Formula: see text] is bounded by [Formula: see text] for [Formula: see text].

We study a problem motivated by a question related to quantum error-correcting codes. Combinatorially, it involves the graph parameter $f(G)=\min\{|A|+|\{x\in V\setminus A:d_A(x)$ is $\text{odd}\}|:A\neq\emptyset\}$, where V is the vertex set of G and $d_A(x)$ is the number of neighbors of x in A. We give asymptotically tight estimates of f for the random graph $G_{n,p}$ when p is constant. Also, if $f(n)=\max\{f(G):\,|V(G)|=n\}$, then we show that $f(n)\leq(0.382+o(1))n$.

A d-simplex is a collection of $d+1$ sets such that every d of them have nonempty intersection and the intersection of all of them is empty. A strong d-simplex is a collection of $d+2$ sets $A,A_1,\dots,A_{d+1}$ such that $\{A_1,\dots,A_{d+1}\}$ is a d-simplex, while A contains an element of $\cap_{j\neq i}A_j$ for each i, $1\leq i\leq d+1$. Mubayi and Ramadurai [Combin. Probab. Comput., 18 (2009), pp. 441–454] conjectured that if $k\geq d+1\geq3$, $n>k(d+1)/d$, and $\mathcal{F}$ is a family of k-element subsets of an n-element set that contains no strong d-simplex, then $|\mathcal{F}|\leq{n-1\choose k-1}$ with equality only when $\mathcal{F}$ is a star. We prove their conjecture when $k\geq d+2$ and n is large. The case $k=d+1$ was solved in [M. Feng and X. J. Liu, Discrete Math., 310 (2010), pp. 1645–1647] and [Z. Füredi, private communication, St. Paul, MN, 2010]. Our result also yields a new proof of a result of Frankl and Füredi [J. Combin. Theory Ser. A, 45 (1987), pp. 226–262] when $k\geq d+2$ and n is large.

In an Achlioptas process two random pairs of $\{1,\dots,n\}$ arrive in each round and the player has to choose one of them. We study the very restrictive version where a player's decisions cannot depend on the previous history and only one vertex from the two random edges is revealed. We prove that the player can create a giant component in $(2\sqrt{5}-4+o(1))n=(0.4721\ldots+o(1))n$ rounds and that this is the best possible. On the other hand, if the player wants to delay the appearance of a giant, then the optimal bound is $(1/2+o(1))n$, the same as in the Erdős–Rényi model.

Abstract We say that a first order formula Φ distinguishes a structure M over a vocabulary L from another structure M′ over the same vocabulary if Φ is true on M but false on M′. A formula Φ defines an L-structure M if Φ distinguishes M from any other non-isomorphic L-structure M′. A formula Φ identifies an n-element L-structure M if Φ distinguishes M from any other non-isomorphic n-element L-structure M′. We prove that every n-element structure M is identifiable by a formula with quantifier rank less than and at most one quantifier alternation, where k is the maximum relation arity of M. Moreover, if the automorphism group of M contains no transposition of two elements, the same result holds for definability rather than identification. The Bernays-Schönfinkel class consists of prenex formulas in which the existential quantifiers all precede the universal quantifiers. We prove that every n-element structure M is identifiable by a formula in the Bernays-Schönfinkel class with less than quantifiers. If in this class of identifying formulas we restrict the number of universal quantifiers to k, then less than quantifiers suffice to identify M and. as long as we keep the number of universal quantifiers bounded by a constant, at total quantifiers are necessary.

We show that $\lim_{n\to\infty}\hat r(F_{1,n},\dots,F_{q,n},F_{q+1},\dots,F_{r})/n$ exists, where the bipartite graphs $F_{q+1},\dots,F_r$ do not depend on n while, for $1\le i\le q$, $F_{i,n}$ is obtained from some bipartite graph $F_i$ with parts $V_1\cup V_2=V(F_i)$ by duplicating each vertex $v\in V_2$ $(c_v+o(1))n$ times for some real $c_v > 0$. In fact, the limit is the minimum of a certain mixed integer program. Using the Farkas lemma we show how to compute it when each forbidden graph is a complete bipartite graph, in particular answering the question of Erdos, Faudree, Rousseau, and Schelp [Period.\ Math.\ Hungar., 9 (1978), pp. 145--161], who asked for the asymptotics of $\hat r(K_{s,n},K_{s,n})$ for fixed s and large n. Also, we prove (for all sufficiently large n) the conjecture of Faudree, Rousseau, and Sheehan in [Graph Theory and Combinatorics, B. Bollobas, ed., Cambridge University Press, Cambridge, UK, 1984, pp. 273--281] that $\hat r(K_{2,n},K_{2,n}) =18n-15$.