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.

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.

We study combinatorial parameters of a recently introduced bootstrap percolation problem in finite projective planes. We present sharp results on the size of the minimum percolating sets and the maximal nonpercolating sets. Additional results on the minimal and maximal percolation time as well as on the critical probability in the projective plane are also presented.

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.

For a property $\Gamma$ and a family of sets ${\mathcal F}$, let $f({\mathcal F},\Gamma)$ be the size of the largest subfamily of ${\mathcal F}$ having property $\Gamma$. For a positive integer m, let $f(m,\Gamma)$ be the minimum of $f({\mathcal F},\Gamma)$ over all families of size m. A family ${\mathcal F}$ is said to be $B_d$-free if it has no subfamily ${\mathcal F}'=\{F_I: I \subseteq [d]\}$ of $2^d$ distinct sets such that for every $I,J \subseteq [d]$, both $F_I \cup F_J=F_{I \cup J}$ and $F_I \cap F_J = F_{I \cap J}$ hold. A family ${\mathcal F}$ is a-union-free if $F_1\cup \dots \cup F_a \neq F_{a+1}$ whenever $F_1,\dots,F_{a+1}$ are distinct sets in ${\mathcal F}$. We verify a conjecture of Erdős and Shelah that $f(m, B_2\text{\rm -free})=\Theta(m^{2/3})$. We also obtain lower and upper bounds for $f(m, B_d\text{\rm -free})$ and $f(m,a\text{\rm -union free})$.

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}$.

The l-chain profile vector of a set system ${\cal F}$ on an underlying set X of size n is defined to be the vector of length ${n+1 \choose l}$ in which the $\alpha$th component ($\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_l) 0 \leq \alpha_1 < \alpha_2 <\cdots< \alpha_l \leq n$) is the number of l-chains in ${\cal F}$ with the smallest set having size $\alpha_1$, the second smallest $\alpha_2$, and so on. We modify the method of Erdős, Frankl, and Katona to determine the l-chain profile polytope of some sets of families including k-Sperner, complement-free, and complement-free k-Sperner families.