Source author record

Mikhail Lavrov

Mikhail Lavrov appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO math.GT math.SG

Catalog footprint

What is connected

8works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Conditions for a bigraph to be super-cyclic

A hypergraph $\mathcal H$ is super-pancyclic if for each $A \subseteq V(\mathcal H)$ with $|A| \geq 3$, $\mathcal H$ contains a Berge cycle with base vertex set $A$. We present two natural necessary conditions for a hypergraph to be super-pancyclic, and show that in several classes of hypergraphs these necessary conditions are also sufficient for this. In particular, they are sufficient for every hypergraph $\mathcal H$ with $ δ(\mathcal H)\geq \max\{|V(\mathcal H)|, \frac{|E(\mathcal H)|+10}{4}\}$. We also consider super-cyclic bipartite graphs: those are $(X,Y)$-bigraphs $G$ such that for each $A \subseteq X$ with $|A| \geq 3$, $G$ has a cycle $C_A$ such that $V(C_A)\cap X=A$. Such graphs are incidence graphs of super-pancyclic hypergraphs, and our proofs use the language of such graphs.

preprint2020arXiv

Longest cycles in 3-connected hypergraphs and bipartite graphs

In the language of hypergraphs, our main result is a Dirac-type bound: we prove that every $3$-connected hypergraph $H$ with $ δ(H)\geq \max\{|V(H)|, \frac{|E(H)|+10}{4}\}$ has a hamiltonian Berge cycle. This is sharp and refines a conjecture by Jackson from 1981 (in the language of bipartite graphs). Our proofs are in the language of bipartite graphs, since the incidence graph of each hypergraph is bipartite.

preprint2019arXiv

Making $K_{r+1}$-Free Graphs $r$-partite

The Erdős-Simonovits stability theorem states that for all ε>0 there exists α>0 such that if G is a K_{r+1}-free graph on n vertices with e(G) > ex(n,K_{r+1}) - αn^2, then one can remove εn^2 edges from G to obtain an r-partite graph. Füredi gave a short proof that one can choose α=ε. We give a bound for the relationship of αand \varepsilon which is asymptotically sharp as ε\to 0.

preprint2015arXiv

An upper bound for the Hales-Jewett number HJ(4,2)

We show that for $n$ at least $10^{11}$, any 2-coloring of the $n$-dimensional grid $[4]^n$ contains a monochromatic combinatorial line. This is a special case of the Hales-Jewett Theorem, to which the best known general upper bound is due to Shelah; Shelah's recursion gives an upper bound between $2 \uparrow \uparrow 7$ and $2 \uparrow \uparrow 8$ for the case we consider, and no better value was previously known.

preprint2014arXiv

Hamiltonian increasing paths in random edge orderings

If the edges of the complete graph $K_n$ are totally ordered, a simple path whose edges are in ascending order is called increasing. The worst-case length of the longest increasing path has remained an open problem for several decades, with asymptotic bounds between $\sqrt{n}$ (Graham and Kleitman, 1973) and $n/2$ (Calderbank, Chung, and Sturtevant, 1984). We consider the average case, when the ordering is chosen uniformly at random. We discover the surprising result that in the random setting, an increasing path of the maximum possible length of $n-1$ exists with probability at least about $1/e$. We also prove that with probability $1-o(1)$, there is an increasing path of length at least $0.85n$, suggesting that this Hamiltonian (or near-Hamiltonian) phenomenon may hold asymptotically almost surely.

preprint2013arXiv

Graham's Number is Less Than 2^^^6

In [5] Graham and Rothschild consider a geometric Ramsey problem: finding the least n such that if all edges of the complete graph on the points {+1,-1}^n are 2-colored, there exist 4 coplanar points such that the 6 edges between them are monochromatic. They give an explicit upper bound: F(F(F(F(F(F(F(12))))))), where F(m) = 2^^(m)^^3, an extremely fast-growing function. By reducing the problem to a variant of the Hales-Jewett problem, we find an upper bound which is between F(4) and F(5).

preprint2012arXiv

On the S^1 x S^2 HOMFLY-PT invariant and Legendrian links

In \cite{GZ}, Gilmer and Zhong established the existence of an invariant for links in $S^1\times S^2$ which is a rational function in variables $a$ and $s$ and satisfies the HOMFLY-PT skein relations. We give formulas for evaluating this invariant in terms of a standard, geometrically simple basis for the HOMFLY-PT skein module of the solid torus. This allows computation of the invariant for arbitrary links in $S^1\times S^2$ and shows that the invariant is in fact a Laurent polynomial in $a$ and $z= s -s^{-1}$. Our proof uses connections between HOMFLY-PT skein modules and invariants of Legendrian links. As a corollary, we extend HOMFLY-PT polynomial estimates for the Thurston-Bennequin number to Legendrian links in $S^1\times S^2$ with its tight contact structure.

preprint2011arXiv

Generalized normal rulings and invariants of Legendrian solid torus links

For Legendrian links in the 1-jet space of $S^1$ we show that the 1-graded ruling polynomial may be recovered from the Kauffman skein module. For such links a generalization of the notion of normal ruling is introduced. We show that the existence of such a generalized normal ruling is equivalent to sharpness of the Kauffman polynomial estimate for the Thurston-Bennequin number as well as to the existence of an ungraded augmentation of the Chekanov-Eliashberg DGA. Parallel results involving the HOMFLY-PT polynomial and 2-graded generalized normal rulings are established.