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.

Abstract. Given a graph [Formula: see text], a Berge copy of [Formula: see text] is a hypergraph obtained by enlarging the edges arbitrarily. Győri [ Combin. Probab. Comput., 15 (2006), pp. 185–191] showed that for [Formula: see text] or [Formula: see text], an [Formula: see text]-uniform [Formula: see text]-vertex Berge triangle-free hypergraph has at most [Formula: see text] hyperedges if [Formula: see text] is large enough, and this bound is sharp. The book graph [Formula: see text] consists of [Formula: see text] triangles sharing an edge. Very recently, Ghosh et al. [ Discrete Math., 347 (2024), 113828] showed that a 3-uniform [Formula: see text]-vertex Berge [Formula: see text]-free hypergraph has at most [Formula: see text] hyperedges if [Formula: see text] is large enough. They conjectured that this bound can be improved to [Formula: see text]. We prove this conjecture for [Formula: see text] and disprove it for [Formula: see text] by proving the sharp bound [Formula: see text]. We also consider larger uniformity and determine the largest number of Berge [Formula: see text]-free [Formula: see text]-uniform hypergraphs besides an additive term [Formula: see text]. We obtain a similar bound if the Berge [Formula: see text]-fan ([Formula: see text] triangles sharing a vertex) is forbidden.

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).

Abstract. The profile vector of a family [Formula: see text] of subsets of an [Formula: see text]-element set is [Formula: see text], where [Formula: see text] denotes the number of the [Formula: see text]-element members of [Formula: see text]. In this paper we determine the extreme points of the set of profile vectors for the class of nontrivial intersecting families.

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.

For a graph G, a hypergraph $\mathcal{H}$ is a Berge copy of G (or a Berge-G in short) if there is a bijection $f : E(G) \rightarrow E(\mathcal{H})$ such that for each $e \in E(G)$ we have $e \subseteq f(e)$. We denote the family of r-uniform hypergraphs that are Berge copies of G by $B^rG$. For families of r-uniform hypergraphs $\mathbf{H}$ and $\mathbf{H}'$, we denote by $R(\mathbf{H},\mathbf{H}')$ the smallest number n such that in any red-blue coloring of the (hyper)edges of $\mathcal{K}_n^r$ (the complete r-uniform hypergraph on n vertices) there is a monochromatic blue copy of a hypergraph in $\mathbf{H}$ or a monochromatic red copy of a hypergraph in $\mathbf{H}'$. $R^c(\mathbf{H})$ denotes the smallest number n such that in any coloring of the hyperedges of $\mathcal{K}_n^r$ with c colors, there is a monochromatic copy of a hypergraph in $\mathbf{H}$. In this paper we initiate the general study of the Ramsey problem for Berge hypergraphs, and show that if $r> 2c$, then $R^c(B^rK_n)=n$. In the case r = 2c, we show that $R^c(B^rK_n)=n+1$, and if G is a noncomplete graph on n vertices, then $R^c(B^rG)=n$, assuming n is large enough. In the case $r < 2c$ we also obtain bounds on $R^c(B^rK_n)$. Moreover, we also determine the exact value of $R(B^3T_1,B^3T_2)$ for every pair of trees T_1 and T_2.

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.

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].

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.