BZPEER

preprint2022arXiv

Connected Turán number of trees

As a variant of the much studied Turán number, $ex(n,F)$ , the largest number of edges that an $n$ -vertex $F$ -free graph may contain, we introduce the connected Turán number $ex_c(n,F)$ , the largest number of edges that an $n$ -vertex connected $F$ -free graph may contain. We focus on the case where the forbidden graph is a tree. The celebrated conjecture of Erdős and Sós states that for any tree $T$ , we have $ex(n,T)\le(|T|-2)\frac{n}{2}$ . We address the problem how much smaller $ex_c(n,T)$ can be, what is the smallest possible ratio of $ex_c(n,T)$ and $(|T|-2)\frac{n}{2}$ as $|T|$ grows. We also determine the exact value of $ex_c(n,T)$ for small trees, in particular for all trees with at most six vertices. We introduce general constructions of connected $T$ -free graphs based on graph parameters as longest path, matching number, branching number, etc.

preprint2022arXiv

Generalized Turán results for intersecting cliques

For fixed graphs $F$ and $H$ , the generalized Turán problem asks for the maximum number $ex(n,H,F)$ of copies of $H$ that an $n$ -vertex $F$ -free graph can have. In this paper, we focus on cases with $F$ being $B_{r,s}$ , the graph consisting of two cliques of size $s$ sharing $r$ common vertices. We determine $ex(n,K_t,B_{r,0})$ , $ex(n,K_t,B_{r,1})$ and $ex(n,K_{a,b},B_{3,1})$ for all values of $a,b,r,t$ if $n$ is large enough.

preprint2022arXiv

Induced and non-induced poset saturation problems

A subfamily $\mathcal{G}\subseteq \mathcal{F}\subseteq 2^{[n]}$ of sets is a non-induced (weak) copy of a poset $P$ in $\mathcal{F}$ if there exists a bijection $i:P\rightarrow \mathcal{G}$ such that $p\le_P q$ implies $i(p)\subseteq i(q)$ . In the case where in addition $p\le_P q$ holds if and only if $i(p)\subseteq i(q)$ , then $\mathcal{G}$ is an induced (strong) copy of $P$ in $\mathcal{F}$ . We consider the minimum number $sat(n,P)$ [resp.\ $sat^*(n,P)$ ] of sets that a family $\mathcal{F}\subseteq 2^{[n]}$ can have without containing a non-induced [induced] copy of $P$ and being maximal with respect to this property, i.e., the addition of any $G\in 2^{[n]}\setminus \mathcal{F}$ creates a non-induced [induced] copy of $P$ . We prove for any finite poset $P$ that $sat(n,P)\le 2^{|P|-2}$ , a bound independent of the size $n$ of the ground set. For induced copies of $P$ , there is a dichotomy: for any poset $P$ either $sat^*(n,P)\le K_P$ for some constant depending only on $P$ or $sat^*(n,P)\ge \log_2 n$ . We classify several posets according to this dichotomy, and also show better upper and lower bounds on $sat(n,P)$ and $sat^*(n,P)$ for specific classes of posets. Our main new tool is a special ordering of the sets based on the colexicographic order. It turns out that if $P$ is given, processing the sets in this order and adding the sets greedily into our family whenever this does not ruin non-induced [induced] $P$ -freeness, we tend to get a small size non-induced [induced] $P$ -saturating family.

preprint2022arXiv

On the number of maximal independent sets: From Moon-Moser to Hujter-Tuza

We connect two classical results in extremal graph theory concerning the number of maximal independent sets. The maximum number mis $(n)$ of maximal independent sets in an $n$ -vertex graph was determined by Moon and Moser. The maximum number mis $_\bigtriangleup(n)$ of maximal independent sets in an $n$ -vertex triangle-free graph was determined by Hujter and Tuza. We determine the maximum number mis $_t(n)$ of maximal independent sets in an $n$ -vertex graph containing no induced triangle matching of size $t+1$ . We also reprove a stability result of Kahn and Park on the maximum number mis $_{\bigtriangleup,t}(n)$ of maximal independent sets in an $n$ -vertex triangle-free graphs containing no induced matching of size $t+1$ .

preprint2022arXiv

Triangles in intersecting families

We prove the following the generalized Turán type result. A collection $\mathcal{T}$ of $r$ sets is an $r$ -triangle if for every $T_1,T_2,\dots,T_{r-1}\in \mathcal{T}$ we have $\cap_{i=1}^{r-1}T_i\neq\emptyset$ , but $\cap_{T\in \mathcal{T}}T$ is empty. A family $\mathcal{F}$ of sets is $r$ -wise intersecting if for any $F_1,F_2,\dots,F_r\in \mathcal{F}$ we have $\cap_{i=1}^rF_i\neq \emptyset$ or equivalently if $\mathcal{F}$ does not contain any $m$ -triangle for $m=2,3,\dots,r$ . We prove that if $n\ge n_0(r,k)$ , then the $r$ -wise intersecting family $\mathcal{F}\subseteq \binom{[n]}{k}$ containing the most number of $(r+1)$ -triangles is isomorphic to $\{F\in \binom{[n]}{k}:|F\cap [r+1]|\ge r\}$ .

preprint2020arXiv

Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets

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(K_n)=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)\le m(G)\le 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\le m(T)\le n-2$ . Our proof uses results about the weighted version of the problem for $K_n$ , which may be of independent interest. We also exhibit a sequence $G_n$ of graphs with $m(G_n)=n-b(n)$ such that $G_n$ has $O(nb(n))$ edges and $n$ vertices.

preprint2020arXiv

Rainbow Ramsey problems for the Boolean lattice

We address the following rainbow Ramsey problem: For posets $P,Q$ what is the smallest number $n$ such that any coloring of the elements of the Boolean lattice $B_n$ either admits a monochromatic copy of $P$ or a rainbow copy of $Q$ . We consider both weak and strong (non-induced and induced) versions of this problem. We also investigate related problems on (partial) $k$ -colorings of $B_n$ that do not admit rainbow antichains of size $k$ .

preprint2020arXiv

Supersaturation, counting, and randomness in forbidden subposet problems

In the area of forbidden subposet problems we look for the largest possible size $La(n,P)$ of a family $\mathcal{F}\subseteq 2^{[n]}$ that does not contain a forbidden inclusion pattern described by $P$ . The main conjecture of the area states that for any finite poset $P$ there exists an integer $e(P)$ such that $La(n,P)=(e(P)+o(1))\binom{n}{\lfloor n/2\rfloor}$ . In this paper, we formulate three strengthenings of this conjecture and prove them for some specific classes of posets. (The parameters $x(P)$ and $d(P)$ are defined in the paper.) $\bullet$ For any finite connected poset $P$ and $\varepsilon>0$ , there exists $δ>0$ and an integer $x(P)$ such that for any $n$ large enough, and $\mathcal{F}\subseteq 2^{[n]}$ of size $(e(P)+\varepsilon)\binom{n}{\lfloor n/2\rfloor}$ , $\mathcal{F}$ contains at least $δn^{x(P)}\binom{n}{\lfloor n/2\rfloor}$ copies of $P$ . $\bullet$ The number of $P$ -free families in $2^{[n]}$ is $2^{(e(P)+o(1))\binom{n}{\lfloor n/2\rfloor}}$ . $\bullet$ For any finite poset $P$ , there exists a positive rational $d(P)$ such that if $p=ω(n^{-d(P)})$ , then the size of the largest $P$ -free family in $\mathcal{P}(n,p)$ is $(e(P)+o(1))p\binom{n}{\lfloor n/2\rfloor}$ with high probability.

preprint2019arXiv

Distribution of colors in Gallai colorings

A Gallai coloring is an edge coloring that avoids triangles colored with three different colors. Given integers $e_1\ge e_2 \ge \dots \ge e_k$ with $\sum_{i=1}^ke_i={n \choose 2}$ for some $n$ , does there exist a Gallai $k$ -coloring of $K_n$ with $e_i$ edges in color $i$ ? In this paper, we give several sufficient conditions and one necessary condition to guarantee a positive answer to the above question. In particular, we prove the existence of a Gallai-coloring if $e_1-e_k\le 1$ and $k \le \lfloor n/2\rfloor$ . We prove that for any integer $k\ge 3$ there is a (unique) integer $g(k)$ with the following property: there exists a Gallai $k$ -coloring of $K_n$ with $e_i$ edges in color $i$ for every $e_1\le\dots \le e_k$ satisfying $\sum_{i=1}^ke_i={n\choose 2}$ , if and only if $n\ge g(k)$ . We show that $g(3)=5$ , $g(4)=8$ , and $2k-2\le g(k)\le 8k^2+1$ for every $k\ge 3$ .

preprint2016arXiv

Dominating sequences in grid-like and toroidal graphs

A longest sequence $S$ of distinct vertices of a graph $G$ such that each vertex of $S$ dominates some vertex that is not dominated by its preceding vertices, is called a Grundy dominating sequence; the length of $S$ is the Grundy domination number of $G$ . In this paper we study the Grundy domination number in the four standard graph products: the Cartesian, the lexicographic, the direct, and the strong product. For each of the products we present a lower bound for the Grundy domination number which turns out to be exact for the lexicographic product and is conjectured to be exact for the strong product. In most of the cases exact Grundy domination numbers are determined for products of paths and/or cycles.

preprint2016arXiv

Finding a non-minority ball with majority answers

Suppose we are given a set of $n$ balls $\{b_1,\ldots,b_n\}$ each colored either red or blue in some way unknown to us. To find out some information about the colors, we can query any triple of balls $\{b_{i_1},b_{i_2},b_{i_3}\}$ . As an answer to such a query we obtain (the index of) a {\em majority ball}, that is, a ball whose color is the same as the color of another ball from the triple. Our goal is to find a {\em non-minority ball}, that is, a ball whose color occurs at least $\frac n2$ times among the $n$ balls. We show that the minimum number of queries needed to solve this problem is $Θ(n)$ in the adaptive case and $Θ(n^3)$ in the non-adaptive case. We also consider some related problems.

preprint2016arXiv

Line Percolation in Finite Projective Planes

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 non-percolating sets. Additional results on the minimal and maximal percolation time as well as on the critical probability in the projective plane are also presented.

preprint2016arXiv

On the number of cycles in a graph with restricted cycle lengths

Let $L$ be a set of positive integers. We call a (directed) graph $G$ an $L$ \emph{-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)=Θ_L(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)=Θ_L(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.

preprint2016arXiv

The minimum number of vertices in uniform hypergraphs with given domination number

The \textit{domination number} $γ(\mathcal{H})$ of a hypergraph $\mathcal{H}=(V(\mathcal{H}),E(\mathcal{H})$ is the minimum size of a subset $D\subset V(\mathcal{H}$ of the vertices such that for every $v\in V(\mathcal{H})\setminus D$ there exist a vertex $d \in D$ and an edge $H\in E(\mathcal{H})$ with $v,d\in H$ . We address the problem of finding the minimum number $n(k,γ)$ of vertices that a $k$ -uniform hypergraph $\mathcal{H}$ can have if $γ(\mathcal{H})\ge γ$ and $\mathcal{H}$ does not contain isolated vertices. We prove that $n(k,γ)=k+Θ(k^{1-1/γ})$ and also consider the $s$ -wise dominating and the distance- $l$ dominating version of the problem. In particular, we show that the minimum number $n_{dc}(k,γ, l)$ of vertices that a connected $k$ -uniform hypergraph with distance- $l$ domination number $γ$ can have is roughly $\frac{kγl}{2}$

preprint2015arXiv

Avoider-Enforcer star games

In this paper, we study $(1 : b)$ Avoider-Enforcer games played on the edge set of the complete graph on $n$ vertices. For every constant $k\geq 3$ we analyse the $k$ -star game, where Avoider tries to avoid claiming $k$ edges incident to the same vertex. We analyse both versions of Avoider-Enforcer games -- the strict and the monotone -- and for each provide explicit winning strategies for both players. We determine the order of magnitude of the threshold biases $f^{mon}_\mathcal{F}$ , $f^-_\mathcal{F}$ and $f^+_\mathcal{F}$ , where $\mathcal{F}$ is the hypergraph of the game.

preprint2015arXiv

On the number of maximal intersecting k-uniform families and further applications of Tuza's set pair method

We study the function $M(n,k)$ which denotes the number of maximal $k$ -uniform intersecting families $F\subseteq \binom{[n]}{k}$ . Improving a bound of Balogh at al. on $M(n,k)$ , we determine the order of magnitude of $\log M(n,k)$ by proving that for any fixed $k$ , $M(n,k) =n^{Θ(\binom{2k}{k})}$ holds. Our proof is based on Tuza's set pair approach. The main idea is to bound the size of the largest possible point set of a cross-intersecting system. We also introduce and investigate some related functions and parameters.

preprint2014arXiv

Search Problems in Vector Spaces

We consider the following $q$ -analog of the basic combinatorial search problem: let $q$ be a prime power and $\GF(q)$ the finite field of $q$ elements. Let $V$ denote an $n$ -dimensional vector space over $\GF(q)$ and let $\mathbf{v}$ be an unknown 1-dimensional subspace of $V$ . We will be interested in determining the minimum number of queries that is needed to find $\mathbf{v}$ provided all queries are subspaces of $V$ and the answer to a query $U$ is YES if $\mathbf{v} \leqslant U$ and NO if $\mathbf{v} \not\leqslant U$ . This number will be denoted by $A(n,q)$ in the adaptive case (when for each queries answers are obtained immediately and later queries might depend on previous answers) and $M(n,q)$ in the non-adaptive case (when all queries must be made in advance). In the case $n=3$ we prove $2q-1=A(3,q)<M(3,q)$ if $q$ is large enough. While for general values of $n$ and $q$ we establish the bounds $n\log q \le A(n,q) \le (1+o(1))nq$ and $(1-o(1))nq \le M(n,q) \le 2nq,$ provided $q$ tends to infinity.

preprint2013arXiv

Nonrepetitive colorings of lexicographic product of graphs

A coloring $c$ of the vertices of a graph $G$ is nonrepetitive if there exists no path $v_1v_2\ldots v_{2l}$ for which $c(v_i)=c(v_{l+i})$ for all $1\le i\le l$ . Given graphs $G$ and $H$ with $|V(H)|=k$ , the lexicographic product $G[H]$ is the graph obtained by substituting every vertex of $G$ by a copy of $H$ , and every edge of $G$ by a copy of $K_{k,k}$ . %Our main results are the following. We prove that for a sufficiently long path $P$ , a nonrepetitive coloring of $P[K_k]$ needs at least $3k+\lfloor k/2\rfloor$ colors. If $k>2$ then we need exactly $2k+1$ colors to nonrepetitively color $P[E_k]$ , where $E_k$ is the empty graph on $k$ vertices. If we further require that every copy of $E_k$ be rainbow-colored and the path $P$ is sufficiently long, then the smallest number of colors needed for $P[E_k]$ is at least $3k+1$ and at most $3k+\lceil k/2\rceil$ . Finally, we define fractional nonrepetitive colorings of graphs and consider the connections between this notion and the above results.

preprint2012arXiv

Majority and Plurality Problems

Given a set of n balls each colored with a color, a ball is said to be majority, k-majority, plurality if its color class has size larger than half of the number of balls, has size at least k, has size larger than any other color class; respectively. We address the problem of finding the minimum number of queries (a comparison of a pair of balls if they have the same color or not) that is needed to decide whether a majority, k-majority or plurality ball exists and if so then show one such ball. We consider both adaptive and non-adaptive strategies and in certain cases, we also address weighted versions of the problems.

preprint2011arXiv

Cross-Sperner families

A pair of families $(\cF,\cG)$ is said to be \emph{cross-Sperner} if there exists no pair of sets $F \in \cF, G \in \cG$ with $F \subseteq G$ or $G \subseteq F$ . There are two ways to measure the size of the pair $(\cF,\cG)$: with the sum $|\cF|+|\cG|$ or with the product $|\cF|\cdot |\cG|$. We show that if $\cF, \cG \subseteq 2^{[n]}$, then $|\cF||\cG| \le 2^{2n-4}$ and $|\cF|+|\cG|$ is maximal if $\cF$ or $\cG$ consists of exactly one set of size $\lceil n/2 \rceil$ provided the size of the ground set $n$ is large enough and both $\cF$ and $\cG$ are non-empty.

preprint2011arXiv

On the ratio of maximum and minimum degree in maximal intersecting families

To study how balanced or unbalanced a maximal intersecting family $\mathcal{F}\subseteq \binom{[n]}{r}$ is we consider the ratio $\mathcal{R}(\mathcal{F})=\frac{Δ(\mathcal{F})}{δ(\mathcal{F})}$ of its maximum and minimum degree. We determine the order of magnitude of the function $m(n,r)$ , the minimum possible value of $\mathcal{R}(\mathcal{F})$ , and establish some lower and upper bounds on the function $M(n,r)$ , the maximum possible value of $\mathcal{R}(\mathcal{F})$ . To obtain constructions that show the bounds on $m(n,r)$ we use a theorem of Blokhuis on the minimum size of a non-trivial blocking set in projective planes.

preprint2011arXiv

Saturating Sperner families

A family $\cF \subseteq 2^{[n]}$ saturates the monotone decreasing property $\cP$ if $\cF$ satisfies $\cP$ and one cannot add any set to $\cF$ such that property $\cP$ is still satisfied by the resulting family. We address the problem of finding the minimum size of a family saturating the $k$ -Sperner property and the minimum size of a family that saturates the Sperner property and that consists only of $l$ -sets and $(l+1)$ -sets.

preprint2011arXiv

Two-part set systems

The two part Sperner theorem of Katona and Kleitman states that if $X$ is an $n$ -element set with partition $X_1 \cup X_2$ , and $\cF$ is a family of subsets of $X$ such that no two sets $A, B \in \cF$ satisfy $A \subset B$ (or $B \subset A$ ) and $A \cap X_i=B \cap X_i$ for some $i$ , then $|\cF| \le {n \choose \lfloor n/2 \rfloor}$. We consider variations of this problem by replacing the Sperner property with the intersection property and considering families that satisfiy various combinations of these properties on one or both parts $X_1$ , $X_2$ . Along the way, we prove the following new result which may be of independent interest: let $\cF, \cG$ be families of subsets of an $n$ -element set such that $\cF$ and $\cG$ are both intersecting and cross-Sperner, meaning that if $A \in \cF$ and $B \in \cG$, then $A \not\subset B$ and $B \not\subset A$ . Then $|\cF| +|\cG| < 2^{n-1}$ and there are exponentially many examples showing that this bound is tight.

preprint2010arXiv

Large B_d-free and union-free subfamilies

For a property $Γ$ and a family of sets $\cF$, let $f(\cF,Γ)$ be the size of the largest subfamily of $\cF$ having property $Γ$ . For a positive integer $m$ , let $f(m,Γ)$ be the minimum of $f(\cF,Γ)$ over all families of size $m$ . A family $\cF$ is said to be $B_d$ -free if it has no subfamily $\cF'=\{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 $\cF$ is $a$ -union free if $F_1\cup ... F_a \neq F_{a+1}$ whenever $F_1,..,F_{a+1}$ are distinct sets in $\FF$. We verify a conjecture of Erd\H os and Shelah that $f(m, B_2\text{\rm -free})=Θ(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})$ .

Balázs Patkós

Research overview

Is this your work?

24 publications

Connected Turán number of trees

Generalized Turán results for intersecting cliques

Induced and non-induced poset saturation problems

On the number of maximal independent sets: From Moon-Moser to Hujter-Tuza

Triangles in intersecting families

Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets

Rainbow Ramsey problems for the Boolean lattice

Supersaturation, counting, and randomness in forbidden subposet problems

Distribution of colors in Gallai colorings

Dominating sequences in grid-like and toroidal graphs

Finding a non-minority ball with majority answers

Line Percolation in Finite Projective Planes

On the number of cycles in a graph with restricted cycle lengths

The minimum number of vertices in uniform hypergraphs with given domination number

Avoider-Enforcer star games

On the number of maximal intersecting k-uniform families and further applications of Tuza's set pair method

Search Problems in Vector Spaces

Nonrepetitive colorings of lexicographic product of graphs

Majority and Plurality Problems

Cross-Sperner families

On the ratio of maximum and minimum degree in maximal intersecting families

Saturating Sperner families

Two-part set systems

Large B_d-free and union-free subfamilies

See the researcher in context

Building this map preview