Balázs Patkós

most citedIdentification of a monotone Boolean function with

k

"reasons" as a combinatorial search problem

1 citations · 1 across the 11 of their papers we have counts for

collaborators

12 papers

math.CO2025

Rainbow Turán problems for forbidden subposets

Balázs Patkós

A family $G$ of sets is a copy of a poset $(P, ⩽)$ if $(G, \subseteq)$ is isomorphic to $(P, ⩽)$ . The forbidden subposet problem asks for determini…

cs.DS2025

Finding the diameter of a tree with distance queries

Dániel Gerbner, András Imolay, Kartal Nagy +2

We study the number of distance queries needed to identify certain properties of a hidden tree $T$ on $n$ vertices. A distance query consists of two vertices $x, y$ , and the answer…

math.CO2025

Turán problems for simplicial complexes

Maria Axenovich, Dániel Gerbner, Dingyuan Liu +1

An abstract simplicial complex $F$ is a non-uniform hypergraph without isolated vertices, whose edge set is closed under taking subsets. The extremal number $\mathrm{ex}(n…

math.CO2025

Poset saturation of unions of chains

Shengjin Ji, Balázs Patkós, Erfei Yue

A family $G$ of sets is a(n induced) copy of a poset $P = (P, ⩽)$ if there exists a bijection $b : P \to G$ such that $p ⩽ q$ holds if and only…

math.CO2025

Bipartite Turán number of trees

Yair Caro, Balázs Patkós, Zsolt Tuza

We start a systematic investigation concerning bipartite Turán number for trees. For a graph $F$ and integers $1 \leq a \leq b$ we define: $(i)$ \quad $e x_{b} (a, b, F)$ is the largest…

math.CO2025

Size, diversity, minimum degree, sturdiness, dömdödöm

Balázs Patkós

For a family $F$ of sets and a disjoint pair $A, B$ we let $F (A, B) = {F \in F : A \subseteq F, B \cap F = \emptyset}$ . The \textbf{ $(p, q)$ -dömdöd…

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

A note on the Erdős Matching Conjecture

Ryan R. Martin, Balázs Patkós

The Erd\H os Matching Conjecture states that the maximum size $f (n, k, s)$ of a family $F \subseteq (k [ n ])$ that does not contain $s$ pairwise disjoint sets is $\max…

math.CO2024

Generalized saturation game

Balázs Patkós, Miloš Stojaković, Jelena Stratijev +1

We study the following game version of the generalized graph Turán problem. For two fixed graphs F and H, two players, Max and Mini, alternately claim unclaimed edges of the comple…

math.CO2024

A note on vertex Turán problems in the Kneser cube

Dániel Gerbner, Balázs Patkós

The Kneser cube $K n_{n}$ has vertex set $2^{[n]}$ and two vertices $F, F^{'}$ are joined by an edge if and only if $F \cap F^{'} = \emptyset$ . For a fixed graph $G$ , we are interested in the m…

math.CO2024

Edge mappings of graphs: Turán type parameters

Yair Caro, Balázs Patkós, Zsolt Tuza +1

In this paper, we address problems related to parameters concerning edge mappings of graphs. The quantity $h (n, G)$ is defined to be the maximum number of edges in an $n$ -vertex gra…

math.CO2024

Edge mappings of graphs: Ramsey type parameters

Yair Caro, Balázs Patkós, Zsolt Tuza +1

In this paper, we launch a systematic study of parameters concerning edge mappings of graphs. Inspired by Ramsey's theorem, the quantity $m (G, H)$ is defined to be the smallest inte…