Domagoj Bradač

activity

20192026

most citedRobust Algorithms for the Secretary Problem

4 citations · 6 across the 10 of their papers we have counts for

collaborators

16 papers

math.CO2026

On the asymptotics of the Erdős-Rogers function

Domagoj Bradač, Oliver Janzer, Rik Sarkar

The Erdős-Rogers function $f_{ℓ, s} (n)$ is the largest order of a $K_{ℓ}$ -free induced subgraph guaranteed to exist in every $K_{s}$ -free graph on $n$ vertices. While this functio…

math.CO2025

Lower bounds for Ramsey numbers of bounded degree hypergraphs

Domagoj Bradač, Zach Hunter, Benny Sudakov

We prove that, for all $k \geq 3,$ and any integers $Δ, n$ with $n \geq Δ,$ there exists a $k$ -uniform hypergraph on $n$ vertices with maximum degree at most $Δ$ whose $4$ -color Rams…

math.CO2024

Clique density vs blowups

Domagoj Bradač, Hong Liu, Zhuo Wu +1

A well-known theorem of Nikiforov asserts that any graph with a positive $K_{r}$ -density contains a logarithmic blowup of $K_{r}$ . In this paper, we explore variants of Nikiforov's r…

math.CO2024

On a question of Erdős and Nešetřil about minimal cuts in a graph

Domagoj Bradač

Answering a question of Erdős and Nešetřil, we show that the maximum number of inclusion-wise minimal vertex cuts in a graph on $n$ vertices is at most $1.889 9^{n}$ for large enough…

math.CO2023

The growth rate of multicolor Ramsey numbers of $3$ -graphs

Domagoj Bradač, Jacob Fox, Benny Sudakov

The $q$ -color Ramsey number of a $k$ -uniform hypergraph $G,$ denoted $r (G; q)$ , is the minimum integer $N$ such that any coloring of the edges of the complete $k$ -uniform hypergraph…

math.CO2023

Ramsey numbers of hypergraphs of a given size

Domagoj Bradač, Jacob Fox, Benny Sudakov

The $q$ -color Ramsey number of a $k$ -uniform hypergraph $H$ is the minimum integer $N$ such that any $q$ -coloring of the complete $k$ -uniform hypergraph on $N$ vertices contains a…

math.CO2023

Large cliques or co-cliques in hypergraphs with forbidden order-size pairs

Maria Axenovich, Domagoj Bradač, Lior Gishboliner +2

The well-known Erdős-Hajnal conjecture states that for any graph $F$ , there exists $ε > 0$ such that every $n$ -vertex graph $G$ that contains no induced copy of $F$ has a homogeneous…

math.CO2023

Minimum Degree Threshold for $H$ -factors with High Discrepancy

Domagoj Bradač, Micha Christoph, Lior Gishboliner

Given a graph $H$ , a perfect $H$ -factor in a graph $G$ is a collection of vertex-disjoint copies of $H$ spanning $G$ . Kühn and Osthus showed that the minimum degree threshold for a…

math.CO2023★ 2 cited

Weighted Turán theorems with applications to Ramsey-Turán type of problems

József Balogh, Domagoj Bradač, Bernard Lidický

We study extensions of Turán Theorem in edge-weighted settings. A particular case of interest is when constraints on the weight of an edge come from the order of the largest clique…

math.CO2023

Effective bounds for induced size-Ramsey numbers of cycles

Domagoj Bradač, Nemanja Draganić, Benny Sudakov

The induced size-Ramsey number $r^_{ind}^{k} (H)$ of a graph $H$ is the smallest number of edges a (host) graph $G$ can have such that for any $k$ -coloring of its edges, the…

math.CO2022

Asymptotics of the hypergraph bipartite Turán problem

Domagoj Bradač, Lior Gishboliner, Oliver Janzer +1

For positive integers $s, t, r$ , let $K_{s, t}^{(r)}$ denote the $r$ -uniform hypergraph whose vertex set is the union of pairwise disjoint sets $X, Y_{1}, \dots, Y_{t}$ , where $∣ X ∣ = s$ and…

math.CO2022

On Ramsey size-linear graphs and related questions

Domagoj Bradač, Lior Gishboliner, Benny Sudakov

In this paper we prove several results on Ramsey numbers $R (H, F)$ for a fixed graph $H$ and a large graph $F$ , in particular for $F = K_{n}$ . These results extend earlier work of Erd…

math.CO2021

Covering random graphs with monochromatic trees

Domagoj Bradač, Matija Bucić

Given an $r$ -edge-coloured complete graph $K_{n}$ , how many monochromatic connected components does one need in order to cover its vertex set? This natural question is a well-known e…

math.CO2021

Powers of Hamilton cycles of high discrepancy are unavoidable

Domagoj Bradač

The Pósa-Seymour conjecture asserts that every graph on $n$ vertices with minimum degree at least $(1 - 1/ (r + 1)) n$ contains the $r^{t h}$ power of a Hamilton cycle. Komlós, Sárközy…

cs.DS2019★ 4 cited

Robust Algorithms for the Secretary Problem

Domagoj Bradac, Anupam Gupta, Sahil Singla +1

In classical secretary problems, a sequence of $n$ elements arrive in a uniformly random order, and we want to choose a single item, or a set of size $K$ . The random order model al…

cs.DS2019

(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing

Domagoj Bradac, Sahil Singla, Goran Zuzic

Consider a kidney-exchange application where we want to find a max-matching in a random graph. To find whether an edge $e$ exists, we need to perform an expensive test, in which ca…

On the asymptotics of the Erdős-Rogers function

Lower bounds for Ramsey numbers of bounded degree hypergraphs

Clique density vs blowups

On a question of Erdős and Nešetřil about minimal cuts in a graph

The growth rate of multicolor Ramsey numbers of 3-graphs

Ramsey numbers of hypergraphs of a given size

Large cliques or co-cliques in hypergraphs with forbidden order-size pairs

Minimum Degree Threshold for H-factors with High Discrepancy

Weighted Turán theorems with applications to Ramsey-Turán type of problems

Effective bounds for induced size-Ramsey numbers of cycles

Asymptotics of the hypergraph bipartite Turán problem

On Ramsey size-linear graphs and related questions

Covering random graphs with monochromatic trees

Powers of Hamilton cycles of high discrepancy are unavoidable

Robust Algorithms for the Secretary Problem

(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing

The growth rate of multicolor Ramsey numbers of $3$ -graphs

Minimum Degree Threshold for $H$ -factors with High Discrepancy