BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Sergey Norin appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We show that the twin-width of every $n$-vertex $d$-regular graph is at most $n^{\frac{d-2}{2d-2}+o(1)}$ and that almost all $d$-regular graphs attain this bound. More generally, we obtain bounds on the twin-width of sparse Erdős-Renyi and regular random graphs, complementing the bounds in the denser regime due to Ahn, Chakraborti, Hendrey, Kim and Oum.
The "clustered chromatic number" of a class of graphs is the minimum integer $k$ such that for some integer $c$ every graph in the class is $k$-colourable with monochromatic components of size at most $c$. We determine the clustered chromatic number of any minor-closed class with bounded treedepth, and prove a best possible upper bound on the clustered chromatic number of any minor-closed class with bounded pathwidth. As a consequence, we determine the fractional clustered chromatic number of every minor-closed class.
Motivated by Hadwiger's conjecture, we prove that every $n$-vertex graph $G$ with no independent set of size three contains an $\lceil n/2\rceil$-vertex simple minor $H$ with $$0.98688 \cdot \binom{|V(H)|}{2} - o(n^2)$$ edges.
The "extremal function" $c(H)$ of a graph $H$ is the supremum of densities of graphs not containing $H$ as a minor, where the "density" of a graph $G$ is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005), Norin, Reed, Thomason and Wood (2020), and Thomason and Wales (2019) determined the asymptotic behaviour of $c(H)$ for all polynomially dense graphs $H$, as well as almost all graphs $H$ of constant density. We explore the asymptotic behavior of the extremal function in the regime not covered by the above results, where in addition to having constant density the graph $H$ is in a graph class admitting strongly sublinear separators. We establish asymptotically tight bounds in many cases. For example, we prove that for every planar graph $H$, $$c(H) = (1+o(1))\cdot\max\left\{\frac{|V(H)|}{2},|V(H)| - α(H)\right\},$$ extending recent results of Haslegrave, Kim and Liu (2020). We also show that an asymptotically tight bound on the extremal function of graphs in minor-closed families proposed by Haslegrave, Kim and Liu (2020) is equivalent to a well studied open weakening of Hadwiger's conjecture.
We show, under mild hypotheses, that if each element of a finitely generated group acting on a $2$-dimensional $\mathrm{CAT}(0)$ complex has a fixed point, then there is a global fixed point. In particular all actions of finitely generated torsion groups on such complexes have global fixed points. The proofs rely on Masur's theorem on periodic trajectories in rational billiards, and Ballmann-Brin's methods for finding closed geodesics in $2$-dimensional locally $\mathrm{CAT}(0)$ complexes. As another ingredient we prove that the image of an immersed loop in a graph of girth $2π$ with length not commensurable with $π$ has diameter $> π$. This is closely related to a theorem of Dehn on tiling rectangles by squares.
In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\geq 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable. We show that every graph with no $K_t$ minor is $O(t(\log t)^β)$-colorable for every $β> 1/4$, making the first improvement on the order of magnitude of the Kostochka-Thomason bound.
In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. While Hadwiger's conjecture does not hold for list-coloring, the linear weakening is conjectured to be true. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and thus is $O(t\sqrt{\log t})$-list-colorable. Recently, the authors and Song proved that every graph with no $K_t$ minor is $O(t(\log t)^β)$-colorable for every $β> \frac 1 4$. Here, we build on that result to show that every graph with no $K_t$ minor is $O(t(\log t)^β)$-list-colorable for every $β> \frac 1 4$. Our main new tool is an upper bound on the number of vertices in highly connected $K_t$-minor-free graphs: We prove that for every $β> \frac 1 4$, every $Ω(t(\log t)^β)$-connected graph with no $K_t$ minor has $O(t (\log t)^{7/4})$ vertices.
The Hall ratio of a graph $G$ is the maximum value of $v(H) / α(H)$ taken over all non-null subgraphs $H$ of $G$. For any graph, the Hall ratio is a lower-bound on its fractional chromatic number. In this note, we present various constructions of graphs whose fractional chromatic number grows much faster than their Hall ratio. This refutes a conjecture of Harris.
We give a natural sufficient condition for an intersection graph of compact convex sets in R^d to have a balanced separator of sublinear size. This condition generalizes several previous results on sublinear separators in intersection graphs. Furthermore, the argument used to prove the existence of sublinear separators is based on a connection with generalized coloring numbers which has not been previously explored in geometric settings.
We consider the problem of maximizing the number of induced copies of an oriented star $S_{k,\ell}$ in digraphs of given size, where the center of the star has out-degree $k$ and in-degree $\ell$. The case $k\ell=0$ was solved by Huang. Here, we asymptotically solve it for all other oriented stars with at least seven vertices.
A family of graphs $\mathcal{F}$ is hereditary if $\mathcal{F}$ is closed under isomorphism and taking induced subgraphs. The speed of $\mathcal{F}$ is the sequence $\{|\mathcal{F}^n|\}_{n \in \mathbb{N}}$, where $\mathcal{F}^n$ denotes the set of graphs in $\mathcal{F}$ with the vertex set $[n]$. Alon, Balogh, Bollobás and Morris [The structure of almost all graphs in a hereditary property, JCTB 2011] gave a rough description of typical graphs in a hereditary family and used it to show for every proper hereditary family $\mathcal{F}$ there exist $\varepsilon>0$ and an integer $l \geq 1$ such that $$|\mathcal{F}^n| = 2^{(1-1/l)n^2/2+o(n^{2-\varepsilon})}.$$ The main result of this paper gives a more precise description of typical structure for a restricted class of hereditary families. As a consequence we characterize hereditary families with the speed just above the threshold $2^{(1-1/l)n^2/2}$, generalizing a result of Balogh and Butterfield [Excluding induced subgraphs: Critical graphs, RSA 2011].
A graph $G$ is $H$-free if it does not contain an induced subgraph isomorphic to $H$. The study of the typical structure of $H$-free graphs was initiated by Erdős, Kleitman and Rothschild, who have shown that almost all $C_3$-free graphs are bipartite. Since then the typical structure of $H$-free graphs has been determined for several families of graphs $H$, including complete graphs, trees and cycles. Recently, Reed and Scott proposed a conjectural description of the typical structure of $H$-free graphs for all graphs $H$, which extends all previously known results in the area. We construct an infinite family of graphs for which the Reed-Scott conjecture fails, and use the methods we developed in the prequel paper to describe the typical structure of $H$-free graphs for graphs $H$ in this family. Using similar techniques, we construct an infinite family of graphs $H$ for which the maximum size of a homogenous set in a typical $H$-free graph is sublinear in the number of vertices, answering a question of Loebl et al. and Kang et al.
We construct an $S_3$-symmetric probability distribution on $\{(a,b,c) \in \mathbb{Z}_{\geq 0}^3 \: : \: a+b+c =n \}$ such that its marginal achieves the maximum entropy among all probability distributions on $\{0,1,\ldots,n\}$ with mean $n/3$. Existence of such a distribution verifies a conjecture of Kleinberg, Sawin and Speyer, which is motivated by the study of sum-free sets.
The "clustered chromatic number" of a class of graphs is the minimum integer $k$ such that for some integer $c$ every graph in the class is $k$-colourable with monochromatic components of size at most $c$. We prove that for every graph $H$, the clustered chromatic number of the class of $H$-minor-free graphs is tied to the tree-depth of $H$. In particular, if $H$ is connected with tree-depth $t$ then every $H$-minor-free graph is $(2^{t+1}-4)$-colourable with monochromatic components of size at most $c(H)$. This provides the first evidence for a conjecture of Ossona de Mendez, Oum and Wood (2016) about defective colouring of $H$-minor-free graphs. If $t=3$ then we prove that 4 colours suffice, which is best possible. We also determine those minor-closed graph classes with clustered chromatic number 2. Finally, we develop a conjecture for the clustered chromatic number of an arbitrary minor-closed class.
A double star $S(n,m)$ is the graph obtained by joining the center of a star with $n$ leaves to a center of a star with $m$ leaves by an edge. Let $r(S(n,m))$ denote the Ramsey number of the double star $S(n,m)$. In 1979 Grossman, Harary and Klawe have shown that $$r(S(n,m)) = \max\{n+2m+2,2n+2\}$$ for $3 \leq m \leq n\leq \sqrt{2}m$ and $3m \leq n$. They conjectured that equality holds for all $m,n \geq 3$. Using a flag algebra computation, we extend their result showing that $r(S(n,m))\leq n+ 2m + 2$ for $m \leq n \leq 1.699m$. On the other hand, we show that the conjecture fails for $\frac{7}{4}m +o(m)\leq n \leq \frac{105}{41}m-o(m)$. Our examples additionally give a negative answer to a question of Erdős, Faudree, Rousseau and Schelp from 1982.
The Kruskal-Katona theorem together with a theorem of Razborov determine the closure of the set of points defined by the homomorphism density of the edge and the triangle in finite graphs. The boundary of this region is a countable union of algebraic curves, and in particular, it is almost everywhere differentiable. One can more generally consider the region defined by the homomorphism densities of a list of given graphs, and ask whether the boundary is as well-behaved as in the case of the triangle and the edge. Towards answering this question in the negative, we construct examples which show that the restrictions of the boundary to certain hyperplanes can have nowhere differentiable parts.
A set of edges $T$ in a graph $G$ is triangle-independent if $T$ contains at most one edge from each triangle in $G$. Let $α_1(G)$ denote the maximum size of the triangle-independent set in $G$, and let $τ_B(G)$ denote minimum size of a set $F \subseteq E(G)$ such that $G \setminus F$ is bipartite. We prove that $$α_1(G) + τ_B(G) \leq \frac{|V(G)|^2}{4},$$ verifying a conjecture due to Lehel, and independently Puleo, and a slightly weaker conjecture of Erdős, Gallai and Tuza. Further, we characterize the graphs which attain the equality.
Let $ES(n)$ be the minimal integer such that any set of $ES(n)$ points in the plane in general position contains $n$ points in convex position. The problem of estimating $ES(n)$ was first formulated by Erdős and Szekeres, who proved that $ES(n) \leq \binom{2n-4}{n-2}+1$. The current best upper bound, $\lim\sup_{n \to \infty} \frac{ES(n)}{\binom{2n-5}{n-2}}\le \frac{29}{32}$, is due to Vlachos. We improve this to $$\lim\sup_{n \to \infty} \frac{ES(n)}{\binom{2n-5}{n-2}}\le \frac{7}{8}.$$
We study the structure of the stable coefficients of the Jones polynomial of an alternating link. We start by identifying the first four stable coefficients with polynomial invariants of a (reduced) Tait graph of the link projection. This leads us to introduce a free polynomial algebra of invariants of graphs whose elements give invariants of alternating links which strictly refine the first four stable coefficients. We conjecture that all stable coefficients are elements of this algebra, and give experimental evidence for the fifth and sixth stable coefficient. We illustrate our results in tables of all alternating links with at most 10 crossings and all irreducible planar graphs with at most 6 vertices.
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 provide a graph-theoretic characterization of win-lose games that possess $ε$-WSNE with constant cardinality supports. We then apply a result in additive number theory of Haight to construct win-lose games that do not satisfy the requirements of the characterization. These constructions disprove graph theoretic conjectures of Daskalakis, Mehta and Papadimitriou, and Myers.
Erdős conjectured that every triangle-free graph $G$ on $n$ vertices contains a set of $\lfloor n/2 \rfloor$ vertices that spans at most $n^2 /50$ edges. Krivelevich proved the conjecture for graphs with minimum degree at least $\frac{2}{5}n$. Keevash and Sudakov improved this result to graphs with average degree at least $\frac{2}{5}n$. We strengthen these results by showing that the conjecture holds for graphs with minimum degree at least $\frac{5}{14}n$ and for graphs with average degree at least $(\frac{2}{5} - \varepsilon)n$ for some absolute $\varepsilon >0$. Moreover, we show that the conjecture is true for graphs which are close to the Petersen graph in edit distance.
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 classes of graphs with strongly sublinear separators have polynomial expansion. This confirms a conjecture of the first author.
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{comp}(H)}{2}-1,$$ when $H$ is a union of cycles, verifying conjectures of Reed and Wood, and Harvey and Wood. We derive the above result from a theorem which allows us to find two vertex disjoint subgraphs with prescribed densities in a sufficiently dense graph, which might be of independent interest.
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) separates the left side of the cube from the right side. We show that S induces a subgraph of tree-width at least n/sqrt{18}-1. We use a generalization of this claim to prove that the vertex set of Q_n cannot be partitioned to two parts, each of them inducing a subgraph of bounded tree-width.
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 \triangle D_2 \subseteq D_3$. A generalized triangle, $\mathcal{T}_r \in Σ_r$ is an $r$-graph on $\{1,2,\ldots,2r-1\}$ with three edges $D_1, D_2, D_3$, such that $D_1=\{1,2,\dots,r-1, r\}, D_2= \{1, 2, \dots, r-1, r+1 \}$ and $D_3 = \{r, r+1, \dots, 2r-1\}.$ Frankl and Füredi conjectured that for all $r\geq 4$, $ex(n,Σ_r) = ex(n,\mathcal{T}_r )$ for all sufficiently large $n$ and they also proved it for $r=3$. Later, Pikhurko showed that the conjecture holds for $r=4$. In this paper we determine $ex(n,\mathcal{T}_5)$ and $ex(n,\mathcal{T}_6)$ for sufficiently large $n$, proving the conjecture for $r=5,6$.
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 this pair and $r-2$ new vertices. Keevash and Sidorenko~ have previously determined Turán densities of two families of hypergraph extensions. We determine the Turán numbers for these families, using classical stability techniques and new tools introduced in our earlier paper.
We examine strategy-proof elections to select a winner amongst a set of agents, each of whom cares only about winning. This impartial selection problem was introduced independently by Holzman and Moulin and Alon et al. Fisher and Klimm showed that the permutation mechanism is impartial and $1/2$-optimal, that is, it selects an agent who gains, in expectation, at least half the number of votes of most popular agent. Furthermore, they showed the mechanism is $7/12$-optimal if agents cannot abstain in the election. We show that a better guarantee is possible, provided the most popular agent receives at least a large enough, but constant, number of votes. Specifically, we prove that, for any $ε>0$, there is a constant $N_ε$ (independent of the number $n$ of voters) such that, if the maximum number of votes of the most popular agent is at least $N_ε$ then the permutation mechanism is $(\frac{3}{4}-ε)$-optimal. This result is tight. Furthermore, in our main result, we prove that near-optimal impartial mechanisms exist. In particular, there is an impartial mechanism that is $(1-ε)$-optimal, for any $ε>0$, provided that the maximum number of votes of the most popular agent is at least a constant $M_ε$.
In an epsilon-approximate Nash equilibrium, a player can gain at most epsilon in expectation by unilateral deviation. An epsilon well-supported approximate Nash equilibrium has the stronger requirement that every pure strategy used with positive probability must have payoff within epsilon of the best response payoff. Daskalakis, Mehta and Papadimitriou conjectured that every win-lose bimatrix game has a 2/3-well-supported Nash equilibrium that uses supports of cardinality at most three. Indeed, they showed that such an equilibrium will exist subject to the correctness of a graph-theoretic conjecture. Regardless of the correctness of this conjecture, we show that the barrier of a 2/3 payoff guarantee cannot be broken with constant size supports; we construct win-lose games that require supports of cardinality at least Omega((log n)^(1/3)) in any epsilon-well supported equilibrium with epsilon < 2/3. The key tool in showing the validity of the construction is a proof of a bipartite digraph variant of the well-known Caccetta-Haggkvist conjecture. A probabilistic argument shows that there exist epsilon-well-supported equilibria with supports of cardinality O(log n/(epsilon^2)), for any epsilon> 0; thus, the polylogarithmic cardinality bound presented cannot be greatly improved. We also show that for any delta > 0, there exist win-lose games for which no pair of strategies with support sizes at most two is a (1-delta)-well-supported Nash equilibrium. In contrast, every bimatrix game with payoffs in [0,1] has a 1/2-approximate Nash equilibrium where the supports of the players have cardinality at most two.