Source author record

Gyula O. H. Katona

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

10works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Nearly Erdős-Ko-Rado theorems

If a family $\mathcal{F}$ of $k$ -element subsets of an $n$ -element set is pairwise intersecting, $2k\leq n$ then $|\mathcal{F}|\leq {n-1\choose k-1}$ holds by the celebrated Erdős-Ko-Rado theorem. But an intersecting family obviously satisfies the condition ${\ell \choose 2}\leq \sum_{1\leq i<j\leq \ell}|F_i\cap F_j|$ for any $\ell$ distinct members of the family. It has been proved in [5] that even if ${\ell \choose 2}$ is replaced by ${\ell -1 \choose 2}+1$ the conclusion $|\mathcal{F}|\leq {n-1\choose k-1}$ remains valid for large $n$ . However the 1 cannot be omitted, because there is a larger family satisfying that weaker condition. In the present paper we determine the largest size of the family under this weaker condition when $n$ is sufficiently large. All of these are treated in the more general setting of $t$ -intersecting families.

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

Gallai Ramsey number for double stars

Given a graph $G$ and a positive integer $k$ , the \emph{Gallai-Ramsey number} is defined to be the minimum number of vertices $n$ such that any $k$ -edge coloring of $K_n$ contains either a rainbow (all different colored) copy of $G$ or a monochromatic copy of $G$ . In this paper, we obtain general upper and lower bounds on the Gallai-Ramsey numbers for double stars $S(n,m)$ , where $S(n,m)$ is the graph obtained from the union of two stars $K_{1,n}$ and $K_{1,m}$ by adding an edge between their centers. We also provide the sharp result in some cases.

preprint2020arXiv

Largest family without a pair of posets on consecutive levels of the Boolean lattice

Suppose $k \ge 2$ is an integer. Let $Y_k$ be the poset with elements $x_1, x_2, y_1, y_2, \ldots, y_{k-1}$ such that $y_1 < y_2 < \cdots < y_{k-1} < x_1, x_2$ and let $Y_k'$ be the same poset but all relations reversed. We say that a family of subsets of $[n]$ contains a copy of $Y_k$ on consecutive levels if it contains $k+1$ subsets $F_1, F_2, G_1, G_2, \ldots, G_{k-1}$ such that $G_1\subset G_2 \subset \cdots \subset G_{k-1} \subset F_1, F_2$ and $|F_1| = |F_2| = |G_{k-1}|+1 =|G_{k-2}|+ 2= \cdots = |G_{1}|+k-1$ . If both $Y_k$ and $Y'_k$ on consecutive levels are forbidden, the size of the largest such family is denoted by $\mathrm{La}_{\mathrm{c}}(n, Y_k, Y'_k)$ . In this paper, we will determine the exact value of $\mathrm{La}_{\mathrm{c}}(n, Y_k, Y'_k)$ .

preprint2020arXiv

The domination number of the graph defined by two levels of the $n$ -cube, II

Consider all $k$ -element subsets and $\ell$ -element subsets $(k>\ell )$ of an $n$ -element set as vertices of a bipartite graph. Two vertices are adjacent if the corresponding $\ell$ -element set is a subset of the corresponding $k$ -element set. Let $G_{k,\ell}$ denote this graph. The domination number of $G_{k,1}$ was exactly determined by Badakhshian, Katona and Tuza. A conjecture was also stated there on the asymptotic value ( $n$ tending to infinity) of the domination number of $G_{k,2}$ . Here we prove the conjecture, determining the asymptotic value of the domination number $γ(G_{k,2})={k+3\over 2(k-1)(k+1)}n^2+o(n^2)$ .

preprint2020arXiv

The number of triangles is more when they have no common vertex

By the theorem of Mantel $[5]$ it is known that a graph with $n$ vertices and $\lfloor \frac{n^{2}}{4} \rfloor+1$ edges must contain a triangle. A theorem of Erdős gives a strengthening: there are not only one, but at least $\lfloor\frac{n}{2}\rfloor$ triangles. We give a further improvement: if there is no vertex contained by all triangles then there are at least $n-2$ of them. There are some natural generalizations when $(a)$ complete graphs are considered (rather than triangles), $(b)$ the graph has $t$ extra edges (not only one) or $(c)$ it is supposed that there are no $s$ vertices such that every triangle contains one of them. We were not able to prove these generalizations, they are posed as conjectures.

preprint2016arXiv

Around the Complete Intersection Theorem

The celebrated theorem of Ahlswede and Khachatrian determines the maximum size of a family of $k$ -element subsets of an $n$ -element set where the intersection of any two subsets has at least $r$ elements. This survey first gives a historical introduction, then it shows some applications.

preprint2014arXiv

Union-intersecting set systems

Three intersection theorems are proved. First, we determine the size of the largest set system, where the system of the pairwise unions is l-intersecting. Then we investigate set systems where the union of any s sets intersect the union of any t sets. The maximal size of such a set system is determined exactly if s+t<5, and asymptotically if s+t>4. Finally, we exactly determine the maximal size of a k-uniform set system that has the above described (s,t)-union-intersecting property, for large enough n.

preprint2013arXiv

Incomparable copies of a poset in the Boolean lattice

Let $B_n$ be the poset generated by the subsets of $[n]$ with the inclusion as relation and let $P$ be a finite poset. We want to embed $P$ into $B_n$ as many times as possible such that the subsets in different copies are incomparable. The maximum number of such embeddings is asymptotically determined for all finite posets $P$ as $\frac{n \choose \lfloor n/2\rfloor}{M(P)}$ , where $M(P)$ denotes the minimal size of the convex hull of a copy of $P$ . We discuss both weak and strong (induced) embeddings.

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Gyula O. H. Katona

Research overview

Is this your work?

10 publications

Nearly Erdős-Ko-Rado theorems

Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets

Gallai Ramsey number for double stars

Largest family without a pair of posets on consecutive levels of the Boolean lattice

The domination number of the graph defined by two levels of the $n$ -cube, II

The number of triangles is more when they have no common vertex

Around the Complete Intersection Theorem

Union-intersecting set systems

Incomparable copies of a poset in the Boolean lattice

Majority and Plurality Problems

See the researcher in context

Building this map preview

Gyula O. H. Katona

Research overview

Is this your work?

10 publications

Nearly Erdős-Ko-Rado theorems

Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets

Gallai Ramsey number for double stars

Largest family without a pair of posets on consecutive levels of the Boolean lattice

The domination number of the graph defined by two levels of the nnn-cube, II

The number of triangles is more when they have no common vertex

Around the Complete Intersection Theorem

Union-intersecting set systems

Incomparable copies of a poset in the Boolean lattice

Majority and Plurality Problems

See the researcher in context

Building this map preview

The domination number of the graph defined by two levels of the $n$ -cube, II