Dániel Gerbner
YOU?
Author Swipe
View article: A note on strongly and totally chain intersecting families
A note on strongly and totally chain intersecting families Open
Bernáth and Gerbner in 2007 introduced ( p , q )-chain intersecting families of subsets of an n -element underlying set. Those have the property that for any p -chain $$A_1\subsetneq A_2\subsetneq \dots \subsetneq A_p$$ and …
View article: Finding the diameter of a tree with distance queries
Finding the diameter of a tree with distance queries Open
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 is the distance of $x$ and $y$ in $T$. We determine the num…
View article: Turán problems for simplicial complexes
Turán problems for simplicial complexes Open
An abstract simplicial complex $\mathbf{F}$ is a non-uniform hypergraph without isolated vertices, whose edge set is closed under taking subsets. The extremal number $\mathrm{ex}(n,\mathbf{F})$ is the maximum number of edges in an $\mathbf…
View article: Survey of generalized Turán problems -- counting subgraphs
Survey of generalized Turán problems -- counting subgraphs Open
For fixed graphs $H$ and $F$, the \emph{generalized Turán number} $\mathrm{ex}(n,H,F)$ is the maximum possible number of copies of a subgraph $H$ in an $n$-vertex $F$-free graph. This article is a survey of this extremal function whose stu…
View article: Rainbow Turán problems for a matching and any other graph
Rainbow Turán problems for a matching and any other graph Open
For a family of graphs $\cF$, a graph is called $\cF$-free if it does not contain any member of $\cF$ as a subgraph. Given a collection of graphs $(G_1,\ldots,G_t)$ on the same vertex set $V$ of size $n$, a rainbow graph on $V$ is obtained…
View article: On the Turán number of the expansion of the $t$-fan
On the Turán number of the expansion of the $t$-fan Open
The $t$-fan is the graph on $2t+1$ vertices consisting of $t$ triangles which intersect at exactly one common vertex. For a given graph $F$, the $r$-expansion $F^r$ of $F$ is the $r$-uniform hypergraph obtained from $F$ by adding $r-2$ dis…
View article: On Turán problems for suspension hypergraphs
On Turán problems for suspension hypergraphs Open
For a given graph $F$, the $r$-uniform suspension of $F$ is the $r$-uniform hypergraph obtained from $F$ by taking $r-2$ new vertices and adding them to every edge. In this paper, we consider Turán problems on suspension hypergraphs, and w…
View article: Directed Graphs Without Rainbow Stars
Directed Graphs Without Rainbow Stars Open
In a rainbow version of the classical Turán problem one considers multiple graphs on a common vertex set, thinking of each graph as edges in a distinct color, and wants to determine the minimum number of edges in each color which guarantee…
View article: Identification of a monotone Boolean function with $k$ "reasons" as a combinatorial search problem
Identification of a monotone Boolean function with $k$ "reasons" as a combinatorial search problem Open
We study the number of queries needed to identify a monotone Boolean function $f:\{0,1\}^n \rightarrow \{0,1\}$. A query consists of a 0-1-sequence, and the answer is the value of $f$ on that sequence. It is well-known that the number of q…
View article: On Turán-type problems and the abstract chromatic number
On Turán-type problems and the abstract chromatic number Open
In 2020, Coregliano and Razborov introduced a general framework to study limits of combinatorial objects, using logic and model theory. They introduced the abstract chromatic number and proved/reproved multiple Erdős-Stone-Simonovits-type …
View article: On hypergraph Turán problems with bounded matching number
On hypergraph Turán problems with bounded matching number Open
Very recently, Alon and Frankl, and Gerbner studied the maximum number of edges in $n$-vertex $F$-free graphs with bounded matching number, respectively. We consider the analogous Turán problems on hypergraphs with bounded matching number,…
View article: On the number of A-transversals in hypergraphs
On the number of A-transversals in hypergraphs Open
A set S of vertices in a hypergraph is strongly independent if every hyperedge shares at most one vertex with S . We prove a sharp result for the number of maximal strongly independent sets in a 3-uniform hypergraph analogous to the Moon-M…
View article: Cooperation in combinatorial search
Cooperation in combinatorial search Open
In the game theoretical approach of the basic problem in Combinatorial Search an adversary thinks of a defective element d of an n -element pool X , and the questioner needs to find x by asking questions of type is $$d\in Q?$$ for ce…
View article: Generalized Turán results for matchings
Generalized Turán results for matchings Open
Given graphs $H$ and $F$, the generalized Turán number $\mathrm{ex}(n,H,F)$ is the largest number of copies of $H$ in $n$-vertex $F$-free graphs. We study the case when either $H$ or $F$ is a matching. We obtain several asymptotic and exac…
View article: On the extremal graphs in generalized Turán problems
On the extremal graphs in generalized Turán problems Open
Given two graphs H and F, the generalized Turán number ex(n,H,F) is the largest number of copies of H in an n-vertex F-free graph. For every graph F, we present an extremal graph for a generalized Turán problem. More precisely, we present …
View article: Generalized Turán results for disjoint cliques
Generalized Turán results for disjoint cliques Open
The generalized Turán number ex(n,H,F) is the largest number of copies of H in n-vertex F-free graphs. We denote by tF the vertex-disjoint union of t copies of F. Gerbner, Methuku and Vizer in 2019 determined the order of magnitude of ex(n…
View article: On Non-degenerate Berge–Turán Problems
On Non-degenerate Berge–Turán Problems Open
Given a hypergraph $${{\mathcal {H}}}$$ and a graph G , we say that $${{\mathcal {H}}}$$ is a Berge - G if there is a bijection between the hyperedges of $${{\mathcal {H}}}$$ and the edges of G such that each hyperedge contains its i…
View article: On extremal values of some degree-based topological indices with a forbidden or a prescribed subgraph
On extremal values of some degree-based topological indices with a forbidden or a prescribed subgraph Open
Xu in 2011 determined the largest value of the second Zagreb index in an $n$-vertex graph $G$ with clique number $k$, and also the smallest value with the additional assumption that $G$ is connected. We extend these results to other degree…
View article: A note on vertex Turán problems in the Kneser cube
A note on vertex Turán problems in the Kneser cube Open
The Kneser cube $Kn_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 most number $vex(n,G)$ of vertices of $Kn_n$ that span a $G$…
View article: Directed graphs without rainbow stars
Directed graphs without rainbow stars Open
In a rainbow version of the classical Turán problem one considers multiple graphs on a common vertex set, thinking of each graph as edges in a distinct color, and wants to determine the minimum number of edges in each color which guarantee…
View article: Degree powers and number of stars in graphs with a forbidden broom
Degree powers and number of stars in graphs with a forbidden broom Open
Given a graph $G$ with degree sequence $d_1,\dots, d_n$ and a positive integer $r$, let $e_r(G)=\sum_{i=1}^n d_i^r$. We denote by $\mathrm{ex}_r(n,F)$ the largest value of $e_r(G)$ among $n$-vertex $F$-free graphs $G$, and by $\mathrm{ex}(…
View article: On degree powers and counting stars in $F$-free graphs
On degree powers and counting stars in $F$-free graphs Open
Given a positive integer $r$ and a graph $G$ with degree sequence $d_1,\dots,d_n$, we define $e_r(G)=\sum_{i=1}^n d_i^r$. We let $\mathrm{ex}_r(n,F)$ be the largest value of $e_r(G)$ if $G$ is an $n$-vertex $F$-free graph. We show that if …
View article: Some Exact Results for Non-Degenerate Generalized Turán Problems
Some Exact Results for Non-Degenerate Generalized Turán Problems Open
The generalized Turán number $\mathrm{ex}(n,H,F)$ is the maximum number of copies of $H$ in $n$-vertex $F$-free graphs. We consider the case where $\chi(H)<\chi(F)$. There are several exact results on $\mathrm{ex}(n,H,F)$ when the extremal…