Zobrazeno 1 - 10
of 16
pro vyhledávání: '"Dániel Korándi"'
Publikováno v:
Journal of Combinatorial Theory, Series B. 146:96-123
A classical result of Erd\H{o}s, Gy\'arf\'as 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 sh
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::16d00bcee18268d77fe2c4083aea2603
https://doi.org/10.1016/j.jctb.2020.07.005
https://doi.org/10.1016/j.jctb.2020.07.005
Publikováno v:
SIAM Journal on Discrete Mathematics, 34 (4)
A matrix is homogeneous if all of its entries are equal. Let $P$ be a $2\times 2$ zero-one matrix that is not homogeneous. We prove that if an $n\times n$ zero-one matrix $A$ does not contain $P$ as a submatrix, then $A$ has an $cn\times cn$ homogene
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2af3766825b1c183bbc83dea10c14e1d
https://doi.org/10.1137/19m125786x
https://doi.org/10.1137/19m125786x
Publikováno v:
Advances in Combinatorics.
Tur\'an's Theorem says that an extremal $K_{r+1}$-free graph is $r$-partite. The Stability Theorem of Erd\H{o}s and Simonovits shows that if a $K_{r+1}$-free graph with $n$ vertices has close to the maximal $t_r(n)$ edges, then it is close to being $
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3db06cd7a1163f331853eee90cc4cdc2
https://doi.org/10.19086/aic.31079
https://doi.org/10.19086/aic.31079
Publikováno v:
Journal of Combinatorial Theory, Series A. 165:32-43
An ordered graph H is a graph with a linear ordering on its vertex set. The corresponding Turan problem, first studied by Pach and Tardos, asks for the maximum number ex ( n , H ) of edges in an ordered graph on n vertices that does not contain H as
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1595abec9bb854ff2e2041ea75d1ccee
https://doi.org/10.1016/j.jcta.2019.01.006
https://doi.org/10.1016/j.jcta.2019.01.006
Autor:
Alex Scott, Benny Sudakov, Jacob Fox, Frédéric Havet, Nemanja Draganić, Dániel Korándi, François Dross, António Girão, David Munhá Correia, William Lochet
Publikováno v:
Combinatorics, Probability & Computing, 30 (6)
Combinatorics, Probability and Computing
Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2021, pp.1-5. ⟨10.1017/S0963548321000067⟩
Combinatorics, Probability and Computing, 2021, pp.1-5. ⟨10.1017/S0963548321000067⟩
Combinatorics, Probability and Computing
Combinatorics, Probability and Computing, Cambridge University Press (CUP), 2021, pp.1-5. ⟨10.1017/S0963548321000067⟩
Combinatorics, Probability and Computing, 2021, pp.1-5. ⟨10.1017/S0963548321000067⟩
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\~ao. We also give a complete solution for this problem when $k=2$, showing that th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fe6bec25af08cdfa915519509c593489
Publikováno v:
Random Structures & Algorithms. 53:667-691
A classic result of Erdős, Gyarfas and Pyber states that for every coloring of the edges of $K_n$ with $r$ colors, there is a cover of its vertex set by at most $f(r) = O(r^2 \log r)$ vertex-disjoint monochromatic cycles. In particular, the minimum
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c2a00e3fbe3d19c80080050afcda71d3
https://doi.org/10.1002/rsa.20819
https://doi.org/10.1002/rsa.20819
Autor:
Dániel Korándi
Publikováno v:
SIAM Journal on Discrete Mathematics. 32:1261-1264
The $t$-colored rainbow saturation number $rsat_t(n,F)$ is the minimum size of a $t$-edge-colored graph on $n$ vertices that contains no rainbow copy of $F$, but the addition of any missing edge in any color creates such a rainbow copy. Barrus, Ferra
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bc5df7c6f0ac242970774caccb4bc83e
https://doi.org/10.1137/17m1155429
https://doi.org/10.1137/17m1155429
Publikováno v:
Combinatorica, 41
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.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f4780e6d106e87311184492fdbc4f643
Autor:
István Tomon, Dániel Korándi
Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f641c071f0b100aa2d54a8bb6eb7548a
Publikováno v:
European Journal of Combinatorics. 45:12-20
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.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::cd7f1dea76145b9766325aaba38f2105
https://doi.org/10.1016/j.ejc.2014.10.003
https://doi.org/10.1016/j.ejc.2014.10.003