G. Katona

activity

20042026

most citedLargest family without A union B contained in C intersect D

56 citations · 62 across the 23 of their papers we have counts for

collaborators

Showing math.COShow all

26 papers · 1 filter

math.CO2026

Multiplicity for partially ordered sets

Gyula O. H. Katona, Yaping Mao

Let $Q = {Q_{a} : a \geq 1}$ be a nested family of finite posets such that $Q_{a} \subseteq Q_{a + 1}$ and $∣ Q_{a} ∣ < ∣ Q_{a + 1} ∣$ . For a poset $Q$ , let $C_{t} (Q)$ denote the set of…

math.CO2026

Ramsey-Turán theory for partially-ordered sets

Gyula O. H. Katona, Yaping Mao

We introduce weak and strong poset Ramsey-Turán numbers for $t$ -chains in host poset families, focusing on the Boolean lattice family $B = {B_{n} : n \geq 1}$ . For any poset $P…

math.CO2026

Erdős-Gyárfás problem for partially ordered sets

Gyula O. H. Katona, Yaping Mao

Given integers $p, q, t$ with $1 \leq t \leq p$ and $1 \leq q \leq h_{p} (t)$ , a strong $(p, q, t)$ -coloring of the Boolean lattice $B_{n}$ is a coloring of its $t$ -chains such that every induc…

math.CO2026

Intersecting families with bounded intersections

Kristina Ago, Gyula O. H. Katona

Let $F \subset 2^{[n]}$ be an $s$ -uniform family such that every two distinct sets have a nonempty intersection but intersect in at most $k$ elements. By the well-known Ray…

math.CO2026

Most probably trangle-free graphs

Yuhang Bai, Gyula O. H. Katona, Zixuan Yang

The celebrated Mantel's theorem states that any triangle-free graph on $n$ vertices contains at most $⌊ n^{2} /4 ⌋$ edges. It is natural to ask how many triangle…

math.CO2026

Boolean lattice without small rainbow subposets

Gyula O. H. Katona, Yaping Mao, Kenta Ozeki +2

A Boolean lattice $B_{n} = (2^{X}, \leq)$ is the power set of an $n$ -element ground set $X$ equipped with inclusion relation. For two posets $P$ and $Q$ , we…

math.CO2026

Nearly Erdős-Ko-Rado theorems

Gyula O. H. Katona, Jian Wang

If a family $F$ of $k$ -element subsets of an $n$ -element set is pairwise intersecting, $2 k \leq n$ then $∣ F ∣ \leq (k - 1 n - 1)$ holds by the celebrated Erdős-…

math.CO2025

Ramsey numbers for partially-ordered sets

Gyula O. H. Katona, Yaping Mao, Kenta Ozeki +1

We say that a poset $Q$ contains a copy (resp.~an induced copy) of a poset $P$ if there is an injection $f : P \to Q$ such that for any $x, y \in P$ , $f (x) \leq f (y)$ in $Q$ if (resp…

math.CO2025

Finding one excellent element in case of one lie

Aanchal Gupta, Gyula O. H. Katona

An n-element set contains an unknown number of excellent elements, and our goal is to identify at least one of these elements. The members of a family of subsets can be asked if th…

math.CO2024★ 1 cited

Identification of a monotone Boolean function with $k$ "reasons" as a combinatorial search problem

Dániel Gerbner, András Imolay, Gyula O. H. Katona +5

We study the number of queries needed to identify a monotone Boolean function $f : {0, 1}^{n} \to {0, 1}$ . A query consists of a 0-1-sequence, and the answer is the value of…

math.CO2024

The maximum sum of the sizes of all intersections within $m$ -size families

Sumin Huang, Gyula O. H. Katona, Erfei Yue

For a family of sets $F$ , let $ω (F) := \sum_{{A, B} \subset F} ∣ A \cap B ∣$ . In this paper, we prove that provided $n$ is sufficiently large, for any $\mat…

math.CO2023

Towards a Baranyai theorem with additional condition

Gyula O. H. Katona, Gyula Y. Katona

A $(k, ℓ)$ partial partition of an $n$ -element set is a collection of $ℓ$ pairwise disjoint $k$ -element subsets. It is proved that, if $n$ is large enough, one can find $\le…

math.CO2021★ 2 cited

On strengthenings of the intersecting shadow theorem

P. Frankl, G. O. H. Katona

Let $n > k > t \geq j \geq 1$ be integers. Let $X$ be an $n$ -element set, $(k X)$ the collection of its $k$ -subsets. A family $F \subset (k X)$ is called $t$ …

math.CO2020

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

Gyula O. H. Katona, Jimeng Xiao

Suppose $k \geq 2$ is an integer. Let $Y_{k}$ be the poset with elements $x_{1}, x_{2}, y_{1}, y_{2}, \dots, y_{k - 1}$ such that $y_{1} < y_{2} < \dots < y_{k - 1} < x_{1}, x_{2}$ and let $Y_{k}^{'}$ be th…

math.CO2020★ 1 cited

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

Chuanqi Xiao, Gyula O. H. Katona

By the theorem of Mantel $[5]$ it is known that a graph with $n$ vertices and $⌊ \frac{n ^{2}}{4} ⌋ + 1$ edges must contain a triangle. A theorem of Erdős gives a strength…

math.CO2020★ 1 cited

Gallai Ramsey number for double stars

Gyula O. H. Katona, Colton Magnant, Yaping Mao +1

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…

math.CO2019

The Turán number of the square of a path

Chuanqi Xiao, Gyula O. H. Katona, Jimeng Xiao +1

The Turán number of a graph H, ex(n,H), is the maximum number of edges in a graph on n vertices which does not have H as a subgraph. Let P_k be the path with k vertices, the square…

math.CO2019★ 1 cited

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

József Balogh, Gyula O. H. Katona, William Linz +1

Consider all $k$ -element subsets and $ℓ$ -element subsets $(k > ℓ)$ of an $n$ -element set as vertices of a bipartite graph. Two vertices are adjacent if the corresponding $\ell…

math.CO2019

Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets

Gábor Damásdi, Dániel Gerbner, Gyula O. H. Katona +8

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…

math.CO2017

A general 2-part Erd\H os-Ko-Rado theorem

Gyula O. H. Katona

A two-part extension of the famous Erdős-Ko-Rado Theorem is proved. The underlying set is partitioned into $X_{1}$ and $X_{2}$ . Some positive integers $k_{i}, ℓ_{i} (1 \leq i \leq m)$ are…

math.CO2016

Around the Complete Intersection Theorem

Gyula O. H. Katona

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 ha…

math.CO2014

A coding problem for pairs of subsets

Bela Bollobas, Zoltan Furedi, Ida Kantor +2

Let $X$ be an $n$ --element finite set, $0 < k \leq n /2$ an integer. Suppose that ${A_{1}, A_{2}}$ and ${B_{1}, B_{2}}$ are pairs of disjoint $k$ -element subsets of $X$ (that is, $|A_1|=|A…

math.CO2014

Union-intersecting set systems

Gyula O. H. Katona, Dániel T. Nagy

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 s…

math.CO2013

Incomparable copies of a poset in the Boolean lattice

Gyula O. H. Katona, Dániel T. Nagy

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 suc…

Multiplicity for partially ordered sets

Ramsey-Turán theory for partially-ordered sets

Erdős-Gyárfás problem for partially ordered sets

Intersecting families with bounded intersections

Most probably trangle-free graphs

Boolean lattice without small rainbow subposets

Nearly Erdős-Ko-Rado theorems

Ramsey numbers for partially-ordered sets

Finding one excellent element in case of one lie

Identification of a monotone Boolean function with k "reasons" as a combinatorial search problem

The maximum sum of the sizes of all intersections within m-size families

Towards a Baranyai theorem with additional condition

On strengthenings of the intersecting shadow theorem

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

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

Gallai Ramsey number for double stars

The Turán number of the square of a path

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

Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets

A general 2-part Erd\H os-Ko-Rado theorem

Around the Complete Intersection Theorem

A coding problem for pairs of subsets

Union-intersecting set systems

Incomparable copies of a poset in the Boolean lattice

Identification of a monotone Boolean function with $k$ "reasons" as a combinatorial search problem

The maximum sum of the sizes of all intersections within $m$ -size families

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