Source author record

Dániel Korándi

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

ResearcherUnclaimed source record

math.CO math.PR

Catalog footprint

Research overview

9works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Saturation in Random Hypergraphs

Let $K^r_n$ be the complete $r$ -uniform hypergraph on $n$ vertices, that is, the hypergraph whose vertex set is $[n]:=\{1,2,...,n\}$ and whose edge set is $\binom{[n]}{r}$ . We form $G^r(n,p)$ by retaining each edge of $K^r_n$ independently with probability $p$ . An $r$ -uniform hypergraph $H\subseteq G$ is $F$ -saturated if $H$ does not contain any copy of $F$ , but any missing edge of $H$ in $G$ creates a copy of $F$ . Furthermore, we say that $H$ is weakly $F$ -saturated in $G$ if $H$ does not contain any copy of $F$ , but the missing edges of $H$ in $G$ can be added back one-by-one, in some order, such that every edge creates a new copy of $F$ . The smallest number of edges in an $F$ -saturated hypergraph in $G$ is denoted by $sat(G,F)$ , and in a weakly $F$ -saturated hypergraph in $G$ by $wsat(G,F)$ . In 2017, Korándi and Sudakov initiated the study of saturation in random graphs, showing that for constant $p$ , with high probability $sat(G(n,p),K_s)=(1+o(1))n\log_{\frac{1}{1-p}}n$ , and $wsat(G(n,p),K_s)=wsat(K_n,K_s)$ . Generalising their results, in this paper, we solve the suturation problem for random hypergraphs for every $2\le r < s$ and constant $p$ .

preprint2021arXiv

Powers of paths in tournaments

In this short note we prove that every tournament contains the $k$ -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also give a complete solution for this problem when $k=2$ , showing that there is always a square of a directed path of length $\lceil 2n/3 \rceil-1$ , which is best possible.

preprint2020arXiv

Covering graphs by monochromatic trees and Helly-type results for hypergraphs

How many monochromatic paths, cycles or general trees does one need to cover all vertices of a given $r$ -edge-coloured graph $G$ ? These problems were introduced in the 1960s and were intensively studied by various researchers over the last 50 years. In this paper, we establish a connection between this problem and the following natural Helly-type question in hypergraphs. Roughly speaking, this question asks for the maximum number of vertices needed to cover all the edges of a hypergraph $H$ if it is known that any collection of a few edges of $H$ has a small cover. We obtain quite accurate bounds for the hypergraph problem and use them to give some unexpected answers to several questions about covering graphs by monochromatic trees raised and studied by Bal and DeBiasio, Kohayakawa, Mota and Schacht, Lang and Lo, and Girão, Letzter and Sahasrabudhe.

preprint2020arXiv

Minimum degree conditions for monochromatic cycle partitioning

A classical result of Erdős, Gyárfás and Pyber states that any $r$ -edge-coloured complete graph has a partition into $O(r^2 \log r)$ monochromatic cycles. Here we determine the minimum degree threshold for this property. More precisely, we show that there exists a constant $c$ such that any $r$ -edge-coloured graph on $n$ vertices with minimum degree at least $n/2 + c \cdot r \log n$ has a partition into $O(r^2)$ monochromatic cycles. We also provide constructions showing that the minimum degree condition and the number of cycles are essentially tight.

preprint2016arXiv

Domination in 3-tournaments

A 3-tournament is a complete 3-uniform hypergraph where each edge has a special vertex designated as its tail. A vertex set $X$ dominates $T$ if every vertex not in $X$ is contained in an edge whose tail is in $X$ . The domination number of $T$ is the minimum size of such an $X$ . Generalizing well-known results about usual (graph) tournaments, Gyárfás conjectured that there are 3-tournaments with arbitrarily large domination number, and that this is not the case if any four vertices induce two triples with the same tail. In this short note we solve both problems, proving the first conjecture and refuting the second.

preprint2016arXiv

Saturation in random graphs

A graph $H$ is $K_s$ -saturated if it is a maximal $K_s$ -free graph, i.e., $H$ contains no clique on $s$ vertices, but the addition of any missing edge creates one. The minimum number of edges in a $K_s$ -saturated graph was determined over 50 years ago by Zykov and independently by Erdős, Hajnal and Moon. In this paper, we study the random analog of this problem: minimizing the number of edges in a maximal $K_s$ -free subgraph of the Erdős-Rényi random graph $G(n,p)$ . We give asymptotically tight estimates on this minimum, and also provide exact bounds for the related notion of weak saturation in random graphs. Our results reveal some surprising behavior of these parameters.

preprint2016arXiv

Separating path systems

We study separating systems of the edges of a graph where each member of the separating system is a path. We conjecture that every $n$ -vertex graph admits a separating path system of size $O(n)$ and prove this in certain interesting special cases. In particular, we establish this conjecture for random graphs and graphs with linear minimum degree. We also obtain tight bounds on the size of a minimal separating path system in the case of trees.

preprint2015arXiv

A random triadic process

Given a random 3-uniform hypergraph $H=H(n,p)$ on $n$ vertices where each triple independently appears with probability $p$ , consider the following graph process. We start with the star $G_0$ on the same vertex set, containing all the edges incident to some vertex $v_0$ , and repeatedly add an edge $xy$ if there is a vertex $z$ such that $xz$ and $zy$ are already in the graph and $xzy \in H$ . We say that the process propagates if it reaches the complete graph before it terminates. In this paper we prove that the threshold probability for propagation is $p=\frac{1}{2\sqrt{n}}$ . We conclude that $p=\frac{1}{2\sqrt{n}}$ is an upper bound for the threshold probability that a random 2-dimensional simplicial complex is simply connected.

preprint2014arXiv

$K_{s,t}$ -saturated bipartite graphs

An $n$ -by- $n$ bipartite graph is $H$ -saturated if the addition of any missing edge between its two parts creates a new copy of $H$ . In 1964, Erdős, Hajnal and Moon made a conjecture on the minimum number of edges in a $K_{s,s}$ -saturated bipartite graph. This conjecture was proved independently by Wessel and Bollobás in a more general, but ordered, setting: they showed that the minimum number of edges in a $K_{(s,t)}$ -saturated bipartite graph is $n^2-(n-s+1)(n-t+1)$ , where $K_{(s,t)}$ is the "ordered" complete bipartite graph with $s$ vertices in the first color class and $t$ vertices in the second. However, the very natural question of determining the minimum number of edges in the unordered $K_{s,t}$ -saturated case remained unsolved. This problem was considered recently by Moshkovitz and Shapira who also conjectured what its answer should be. In this short paper we give an asymptotically tight bound on the minimum number of edges in a $K_{s,t}$ -saturated bipartite graph, which is only smaller by an additive constant than the conjecture of Moshkovitz and Shapira. We also prove their conjecture for $K_{2,3}$ -saturation, which was the first open case.

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.

Dániel Korándi

Research overview

Is this your work?

9 publications

Saturation in Random Hypergraphs

Powers of paths in tournaments

Covering graphs by monochromatic trees and Helly-type results for hypergraphs

Minimum degree conditions for monochromatic cycle partitioning

Domination in 3-tournaments

Saturation in random graphs

Separating path systems

A random triadic process

$K_{s,t}$ -saturated bipartite graphs

See the researcher in context

Building this map preview

Dániel Korándi

Research overview

Is this your work?

9 publications

Saturation in Random Hypergraphs

Powers of paths in tournaments

Covering graphs by monochromatic trees and Helly-type results for hypergraphs

Minimum degree conditions for monochromatic cycle partitioning

Domination in 3-tournaments

Saturation in random graphs

Separating path systems

A random triadic process

Ks,tK_{s,t}Ks,t​-saturated bipartite graphs

See the researcher in context

Building this map preview

$K_{s,t}$ -saturated bipartite graphs