Author name cluster

Nemanja Skoric

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

SODA Conference 2015 Conference Paper

An algorithmic framework for obtaining lower bounds for random Ramsey problems extended abstract

Rajko Nenadov
Nemanja Skoric
Angelika Steger

In this paper we introduce a general framework for proving lower bounds for various Ramsey type problems within random settings. The main idea is to view the problem from an algorithmic perspective: we aim at providing an algorithm that finds the desired colouring with high probability. Our framework allows to reduce the probabilistic problem of whether the Ramsey property at hand holds for random (hy-per)graphs with edge probability p to a deterministic question of whether there exists a finite graph that forms an obstruction. In the second part of the paper we apply this framework to address and solve various open problems. In particular, we provide a matching lower bound for the result of Friedgut, Rödl and Schacht (2010) and, independently, Conlon and Gowers (2014+) for the classical Ramsey problem for hypergraphs in the case of cliques. A problem that was open for more than 15 years. We also improve a result of Bohman, Frieze, Pikhurko and Smyth (2010) for bounded anti-Ramsey problems in random graphs and extend it to hypergraphs. Finally, we provide matching lower bounds for a proper-colouring version of anti-Ramsey problems introduced by Kohayakawa, Konstadinidis and Mota (2014).

Details

SODA Conference 2015 Conference Paper

Robust hamiltonicity of random directed graphs extended abstract

Asaf Ferber
Rajko Nenadov
Ueli Peter
Andreas Noever
Nemanja Skoric

In his seminal paper from 1952 Dirac showed that the complete graph on n ≥ 3 vertices remains Hamiltonian even if we allow an adversary to remove ⌊ n /2⌋ edges touching each vertex. In 1960 Ghouila-Houri obtained an analogue statement for digraphs by showing that every directed graph on n ≥ 3 vertices with minimum in- and out-degree at least n /2 contains a directed Hamilton cycle. Both statements quantify the robustness of complete graphs (digraphs) with respect to the property of containing a Hamilton cycle. A natural way to generalize such results to arbitrary graphs (digraphs) is using the notion of local resilience. The local resilience of a graph (digraph) G with respect to a property is the maximum number r such that G has the property even if we allow an adversary to remove an r -fraction of (in- and out-going) edges touching each vertex. The theorems of Dirac and Ghouila-Houri state that the local resilience of the complete graph and digraph with respect to Hamiltonicity is 1/2. Recently, this statements have been generalized to random settings. Lee and Sudakov (2012) proved that the local resilience of a random graph with edge probability p = ω (log n / n ) with respect to Hamiltonicity is 1/2 ± o (1). For random directed graphs, Hefetz, Steger and Sudakov (2014+) proved an analogue statement, but only for edge probability. In this paper we significantly improve their result to p = ω (log 8 n / n ), which is optimal up to the polylogarithmic factor.

Details