We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to compute its value, even if we know beforehand that the number of 0’s and 1’s in the input are the same, i.e., when our input is from the middle slice. This answers a question of Byramji. Our proof is non-constructive, but we also propose a concrete candidate function that might have the above property. Our results are related to certain natural discrepancy type questions that, somewhat surprisingly, have not been studied before.

We study exak(n,F), the largest number of edges in an n-vertex graph that contains exactly k copies of a given subgraph F. The case k=0 is the Turán number ex(n,F) that is among the most studied parameters in extremal graph theory. We show that for any F and k, exak(n,F)=(1+o(1))ex(n,F) and determine the exact values of exak(n,K3) and exa1(n,Kr) for n large enough. We also explore a connection to the following well-known problem in search theory. We are given a graph of order n that consists of an unknown copy of F and some isolated vertices. We can ask pairs of vertices as queries, and the answer tells us whether there is an edge between those vertices. Our goal is to describe the graph using as few queries as possible. Aigner and Triesch in 1990 showed that the number of queries needed is at least n2−exa1(n,F). Among other results we show that the number of queries that were answered NO is at least n2−exa1(n,F).

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.

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study the problem of finding a majority vertex (or show that none exists), if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by m(G). It was shown by Saks and Werman that m(Kn)=n−b(n), where b(n) is the number of 1’s in the binary representation of n. In this paper we initiate the study of the problem for general graphs. The obvious bounds for a connected graph G on n vertices are n−b(n)≤m(G)≤n−1. We show that for any tree T on an even number of vertices we have m(T)=n−1, and that for any tree T on an odd number of vertices, we have n−65≤m(T)≤n−2. Our proof uses results about the weighted version of the problem for Kn, which may be of independent interest. We also exhibit a sequence Gn of graphs with m(Gn)=n−b(n) such that Gn has O(nb(n)) edges and n vertices.

We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite graphs. In particular, we show that in every cover of a Young diagram with $\binom{2k}{k}$ steps with generalized rectangles, there is a row or a column in the diagram that is used by at least $k+1$ rectangles and prove that this is best possible. This answers two questions by Kim et al. [ European J. Combin., 86 (2020), 103074], namely, what is the local complete bipartite covering number of a difference graph, and is there a sequence of graphs with a constant local difference graph covering numbers and unbounded local complete bipartite covering numbers? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim et al., we use the results on local covering numbers to provide lower and upper bounds for the local dimension of partially ordered sets of height 2. We discuss the local dimension of some posets related to Boolean lattices and show that the poset induced by the first two layers of the Boolean lattice has local dimension $(1 + o(1))\log_2\log_2 n$. We conclude with some remarks on covering numbers for digraphs and Ferrers dimension.

In many proofs concerning extremal parameters of Berge hypergraphs one starts with analyzing that part of that shadow graph which is contained in many hyperedges. Capturing this phenomenon we introduce two new types of hypergraphs. A hypergraph ${\mathcal H}$ is a $t$-heavy copy of a graph $F$ if there is a copy of $F$ on its vertex set such that each edge of $F$ is contained in at least $t$ hyperedges of ${\mathcal H}$. ${\mathcal H}$ is a $t$-wise Berge copy of $F$ if additionally for distinct edges of $F$ those $t$ hyperedges are distinct. We extend known upper bounds on the Turán number of Berge hypergraphs to the $t$-wise Berge hypergraphs case. We asymptotically determine the Turán number of $t$-heavy and $t$-wise Berge copies of long paths and cycles and exactly determine the Turán number of $t$-heavy and $t$-wise Berge copies of cliques. In the case of 3-uniform hypergraphs, we consider the problem in more details and obtain additional results.