20 citations · 64 across the 12 of their papers we have counts for
15 papers · 1 filter
On a maximal anti-Ramsey conjecture of Burr, Erdős, Graham, and Sós
Matija Bucic, Kaizhe Chen, Jie Ma
Given a graph , the maximal anti-Ramsey function denotes the minimum integer for which there exists an -vertex graph with at least edges admitting an e…
Towards the Erdős-Gallai Cycle Decomposition Conjecture
Matija Bucić, Richard Montgomery
In the 1960's, Erdős and Gallai conjectured that the edges of any -vertex graph can be decomposed into cycles and edges. We improve upon the previous best bound of $O(n\l…
Tight Ramsey bounds for multiple copies of a graph
Matija Bucic, Benny Sudakov
The Ramsey number of a graph is the smallest integer such that any colouring of the edges of a clique on vertices contains a monochromatic copy of . Deter…
Clique minors in graphs with a forbidden subgraph
M. Bucić, J. Fox, B. Sudakov
The classical Hadwiger conjecture dating back to 1940's states that any graph of chromatic number at least has the clique of order as a minor. Hadwiger's conjecture is an e…
Erdős-Szekeres theorem for multidimensional arrays
M. Bucić, B. Sudakov, T. Tran
The classical Erdős-Szekeres theorem dating back almost a hundred years states that any sequence of distinct real numbers contains a monotone subsequence of length .…
Perfect matchings and derangements on graphs
Matija Bucic, Pat Devlin, Mo Hendon +2
We show that each perfect matching in a bipartite graph intersects at least half of the perfect matchings in . This result has equivalent formulations in terms of the perman…
List Ramsey numbers
N. Alon, M. Bucić, T. Kalvari +2
We introduce the list colouring extension of classical Ramsey numbers. We investigate when the two Ramsey numbers are equal, and in general, how far apart they can be from each oth…
Covering graphs by monochromatic trees and Helly-type results for hypergraphs
Matija Bucić, Dániel Korándi, Benny Sudakov
How many monochromatic paths, cycles or general trees does one need to cover all vertices of a given -edge-coloured graph ? These problems were introduced in the 1960s and we…
Multicolour bipartite Ramsey number of paths
Matija Bucic, Shoham Letzter, Benny Sudakov
The -colour bipartite Ramsey number of a bipartite graph is the least integer for which every -edge-coloured complete bipartite graph contains a monochromat…
Monochromatic trees in random tournaments
Matija Bucic, Sven Heberle, Shoham Letzter +1
We prove that, with high probability, in every -edge-colouring of the random tournament on vertices there is a monochromatic copy of every oriented tree of order $O (n / \sq…
Nearly-linear monotone paths in edge-ordered graphs
Matija Bucic, Matthew Kwan, Alexey Pokrovskiy +3
How long a monotone path can one always find in any edge-ordering of the complete graph ? This appealing question was first asked by Chvátal and Komlós in 1971, and has since…
Partition problems in high dimensional boxes
Matija Bucic, Bernard Lidicky, Jason Long +1
Alon, Bohman, Holzman and Kleitman proved that any partition of a -dimensional discrete box into proper sub-boxes must consist of at least sub-boxes. Recently, Leader, Mil…
Directed Ramsey number for trees
Matija Bucic, Shoham Letzter, Benny Sudakov
In this paper, we study Ramsey-type problems for directed graphs. We first consider the -colour oriented Ramsey number of , denoted by , which is the…
Monochromatic paths in random tournaments
Matija Bucić, Shoham Letzter, Benny Sudakov
We prove that, with high probability, any -edge-colouring of a random tournament on vertices contains a monochromatic path of length . This resolves a…
An improved bound for disjoint directed cycles
Matija Bucić
We show that every directed graph with minimum out-degree at least contains at least vertex disjoint cycles. This is an improvement over the result of Alon who showed thi…