Search

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 $ \delta(\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., Comment: 17 pages

Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of $G$ are colored. The game chromatic number \chi_g(G) is the minimum k for which the first player has a winning strategy. The paper \cite{BFS} began the analysis of the asymptotic behavior of this parameter for a random graph G_{n,p}. This paper provides some further analysis for graphs with constant average degree i.e. np=O(1) and for random regular graphs., Comment: Correction

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., Comment: 26 pages, 6 figures