S. Norin

activity

20092026

most citedCounting flags in triangle-free digraphs

25 citations · 246 across the 55 of their papers we have counts for

collaborators

Showing 2015Show all

7 papers · 1 filter

math.CO2015

Treewidth of grid subsets

Eli Berger, Zdenek Dvorak, Sergey Norin

Let Q_n be the graph of n times n times n cube with all non-decreasing diagonals (including the facial ones) in its constituent unit cubes. Suppose that a subset S of V(Q_n) separa…

math.CO2015

Turán numbers of extensions

Sergey Norin, Liana Yepremyan

The extension of an $r$ -uniform hypergraph $G$ is obtained from it by adding for every pair of vertices of $G$ , which is not covered by an edge in $G$ , an extra edge containing thi…

math.CO2015

Erdős-Szekeres without induction

Sergey Norin, Yelena Yuditsky

Let $E S (n)$ be the minimal integer such that any set of $E S (n)$ points in the plane in general position contains $n$ points in convex position. The problem of estimating $E S (n)$ wa…

math.CO2015

The extremal function for disconnected minors

Endre Csóka, Irene Lo, Sergey Norin +2

For a graph $H$ let $c (H)$ denote the supremum of $∣ E (G) ∣/∣ V (G) ∣$ taken over all non-null graphs $G$ not containing $H$ as a minor. We show that $$c(H) \leq \frac{|V(H)|+\mathrm{co…

math.CO2015

Strongly sublinear separators and polynomial expansion

Zdenek Dvorak, Sergey Norin

A result of Plotkin, Rao, and Smith implies that graphs with polynomial expansion have strongly sublinear separators. We prove a converse of this result showing that hereditary cla…

cs.GT2015★ 7 cited

Large Supports are required for Well-Supported Nash Equilibria

Yogesh Anbalagan, Hao Huang, Shachar Lovett +3

We prove that for any constant $k$ and any $ε < 1$ , there exist bimatrix win-lose games for which every $ε$ -WSNE requires supports of cardinality greater than $k$ . To do this, we pro…

math.CO2015

Turán Number of Generalized Triangles

Sergey Norin, Liana Yepremyan

The family $Σ_{r}$ consists of all $r$ -graphs with three edges $D_{1}, D_{2}, D_{3}$ such that $∣ D_{1} \cap D_{2} ∣ = r - 1$ and $D_{1} △ D_{2} \subseteq D_{3}$ . A generalized triangle, $\mathcal{T}…