Krzysztof Choromański

most citedDifferentially- and non-differentially-private random decision trees

18 citations · 23 across the 4 of their papers we have counts for

collaborators

Showing math.COShow all

2 papers · 1 filter

math.CO2014★ 1 cited

The Strong EH-Property and the Erdős-Hajnal Conjecture

Krzysztof Choromanski

The Erdős-Hajnal Conjecture states that for every $H$ there exists a constant $ε (H) > 0$ such that every graph $G$ that does not contain $H$ as an induced subgraph contains a clique…

math.CO2014

All known prime Erdős-Hajnal tournaments satisfy $ε (H) = Ω (\frac{1}{∣ H ∣ ^{5} l o g ( ∣ H ∣ )})$

Krzysztof Choromanski

We prove that there exists $C > 0$ such that $ε (H) \geq \frac{C}{∣ H ∣ ^{5} l o g ( ∣ H ∣ )}$ , where $ε (H)$ is the Erdős-Hajnal coefficient of the tournament $H$ , for every prime tournament $H…

The Strong EH-Property and the Erdős-Hajnal Conjecture

All known prime Erdős-Hajnal tournaments satisfy ε(H)=Ω(∣H∣5log(∣H∣)1​)

All known prime Erdős-Hajnal tournaments satisfy $ε (H) = Ω (\frac{1}{∣ H ∣ ^{5} l o g ( ∣ H ∣ )})$