BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Gyula O. H. Katona

Gyula O. H. Katona contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CODiscrete Mathematics

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

8 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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&#39;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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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&#39;$ 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&#39;_k$ on consecutive levels are forbidden, the size of the largest such family is denoted by $\mathrm{La}_{\mathrm{c}}(n, Y_k, Y&#39;_k)$. In this paper, we will determine the exact value of $\mathrm{La}_{\mathrm{c}}(n, Y_k, Y&#39;_k)$.

0 citations0 reviewsNo code linkedOpen access
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)$.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access