Recent Activity

Jacob Palis Conjecture(Finitude of Attractors)(Dynamical Systems) ★★★★

Author(s):

Conjecture Let $Diff^{r}(M)$ be the space of $C^{r}$ Diffeomorphisms on the connected , compact and boundaryles manifold M and $\chi^{r}(M)$ the space of $C^{r}$ vector fields. There is a dense set $D\subset Diff^{r}(M)$ ( $D\subset \chi^{r}(M)$ ) such that $\forall f\in D$ exhibit a finite number of attractor whose basins cover Lebesgue almost all ambient space $M$

This is a very Deep and Hard problem in Dynamical Systems . It present the dream of the dynamicist mathematicians .

Keywords: Attractors , basins, Finite

Posted by Jailton Viana
updated April 24th, 2013

add new comment

Closing Lemma for Diffeomorphism (Dynamical Systems) ★★★★

Author(s): Charles Pugh

Conjecture Let $f\in Diff^{r}(M)$ and $p\in\omega_{f}$ . Then for any neighborhood $V_{f}\subset Diff^{r}(M)$ there is $g\in V_{f}$ such that $p$ is periodic point of $g$

There is an analogous conjecture for flows ( $C^{r}$ vector fields . In the case of diffeos this was proved by Charles Pugh for $r = 1$ . In the case of Flows this has been solved by Sushei Hayahshy for $r = 1$ . But in the two cases the problem is wide open for $r > 1$

Keywords: Dynamics , Pertubation

Posted by Jailton Viana
updated April 24th, 2013

add new comment

Sub-atomic product of funcoids is a categorical product ★★

Author(s):

Conjecture In the category of continuous funcoids (defined similarly to the category of topological spaces) the following is a direct categorical product:

\item Product morphism is defined similarly to the category of topological spaces. \item Product object is the sub-atomic product. \item Projections are sub-atomic projections.

See details, exact definitions, and attempted proofs here.

Keywords:

Posted by porton
updated April 21st, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Bounding the on-line choice number in terms of the choice number ★★

Author(s): Zhu

Question Are there graphs for which $\text{ch}^{\text{OL}}-\text{ch}$ is arbitrarily large?

Keywords: choosability; list coloring; on-line choosability

Posted by Jon Noel
updated April 11th, 2013

add new comment

Are almost all graphs determined by their spectrum? ★★★

Author(s):

Problem Are almost all graphs uniquely determined by the spectrum of their adjacency matrix?

Keywords: cospectral; graph invariant; spectrum

Posted by mdevos
updated March 26th, 2013

add new comment

Signing a graph to have small magnitude eigenvalues ★★

Author(s): Bilu; Linial

Conjecture If $A$ is the adjacency matrix of a $d$ -regular graph, then there is a symmetric signing of $A$ (i.e. replace some $+1$ entries by $-1$ ) so that the resulting matrix has all eigenvalues of magnitude at most $2 \sqrt{d-1}$ .

Keywords: eigenvalue; expander; Ramanujan graph; signed graph; signing

Posted by mdevos
updated March 24th, 2013

add new comment

Graph Theory » Extremal G.T.

The Bollobás-Eldridge-Catlin Conjecture on graph packing ★★★

Author(s):

Conjecture (BEC-conjecture) If $G_1$ and $G_2$ are $n$ -vertex graphs and $(\Delta(G_1) + 1) (\Delta(G_2) + 1) < n + 1$ , then $G_1$ and $G_2$ pack.

Keywords: graph packing

Posted by asp
updated March 23rd, 2013

add new comment

Graph Theory » Directed Graphs » Tournaments

Decomposing k-arc-strong tournament into k spanning strong digraphs ★★

Author(s): Bang-Jensen; Yeo

Conjecture Every k-arc-strong tournament decomposes into k spanning strong digraphs.

Keywords:

Posted by fhavet
updated March 15th, 2013

add new comment

Graph Theory » Graph Algorithms

PTAS for feedback arc set in tournaments ★★

Author(s): Ailon; Alon

Question Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?

Keywords: feedback arc set; PTAS; tournament

Posted by fhavet
updated March 15th, 2013

add new comment

Graph Theory » Directed Graphs » Tournaments

Partitionning a tournament into k-strongly connected subtournaments. ★★

Author(s): Thomassen

Problem Let $k_1, \dots , k_p$ be positve integer Does there exists an integer $g(k_1, \dots , k_p)$ such that every $g(k_1, \dots , k_p)$ -strong tournament $T$ admits a partition $(V_1\dots , V_p)$ of its vertex set such that the subtournament induced by $V_i$ is a non-trivial $k_i$ -strong for all $1\leq i\leq p$ .

Keywords:

Posted by fhavet
updated March 15th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Weighted colouring of hexagonal graphs. ★★

Author(s): McDiarmid; Reed

Conjecture There is an absolute constant $c$ such that for every hexagonal graph $G$ and vertex weighting $p:V(G)\rightarrow \mathbb{N}$ , $\chi(G,p) \leq \frac{9}{8}\omega(G,p) + c$

Keywords:

Posted by fhavet
updated March 13th, 2013

add new comment

Graph Theory » Coloring » Vertex coloring

Colouring the square of a planar graph ★★

Author(s): Wegner

Conjecture Let $G$ be a planar graph of maximum degree $\Delta$ . The chromatic number of its square is

$7$

$\Delta =3$

$\Delta+5$

$4\leq\Delta\leq 7$

$\left\lfloor\frac32\,\Delta\right\rfloor+1$

$\Delta\ge8$

Keywords:

Posted by fhavet
updated March 13th, 2013

add new comment | 1 attachment

Graph Theory » Coloring » Vertex coloring

List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

Conjecture There is a constant $c$ such that the list chromatic number of any bipartite graph $G$ of maximum degree $\Delta$ is at most $c \log \Delta$ .

Keywords:

Posted by fhavet
updated March 12th, 2013

add new comment

Graph Theory » Basic G.T. » Cycles

Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

Author(s): Alspach; Rosenfeld

Conjecture Every prism over a $3$ -connected cubic planar graph can be decomposed into two Hamilton cycles.

Keywords:

Posted by fhavet
updated March 12th, 2013

add new comment

Graph Theory » Hypergraphs

Turán's problem for hypergraphs ★★

Author(s): Turan

Conjecture Every simple $3$ -uniform hypergraph on $3n$ vertices which contains no complete $3$ -uniform hypergraph on four vertices has at most $\frac12 n^2(5n-3)$ hyperedges.

Conjecture Every simple $3$ -uniform hypergraph on $2n$ vertices which contains no complete $3$ -uniform hypergraph on five vertices has at most $n^2(n-1)$ hyperedges.

Keywords:

Posted by fhavet
updated March 12th, 2013

add new comment

Graph Theory » Basic G.T. » Cycles

4-connected graphs are not uniquely hamiltonian ★★

Author(s): Fleischner

Conjecture Every $4$ -connected graph with a Hamilton cycle has a second Hamilton cycle.

Keywords:

Posted by fhavet
updated March 11th, 2013

add new comment

Graph Theory » Basic G.T. » Cycles

Every prism over a 3-connected planar graph is hamiltonian. ★★

Author(s): Kaiser; Král; Rosenfeld; Ryjácek; Voss

Conjecture If $G$ is a $3$ -connected planar graph, then $G\square K_2$ has a Hamilton cycle.

Keywords:

Posted by fhavet
updated March 11th, 2013

add new comment

Graph Theory » Directed Graphs

Hoàng-Reed Conjecture ★★★

Author(s): Hoang; Reed

Conjecture Every digraph in which each vertex has outdegree at least $k$ contains $k$ directed cycles $C_1, \ldots, C_k$ such that $C_j$ meets $\cup_{i=1}^{j-1}C_i$ in at most one vertex, $2 \leq j \leq k$ .

Keywords:

Posted by fhavet
updated March 11th, 2013

add new comment

Graph Theory » Directed Graphs » Tournaments

Edge-disjoint Hamilton cycles in highly strongly connected tournaments. ★★

Author(s): Thomassen

Conjecture For every $k\geq 2$ , there is an integer $f(k)$ so that every strongly $f(k)$ -connected tournament has $k$ edge-disjoint Hamilton cycles.

Keywords:

Posted by fhavet
updated March 8th, 2013

add new comment

Graph Theory » Directed Graphs

Hamilton cycle in small d-diregular graphs ★★

Author(s): Jackson

An directed graph is $k$ -diregular if every vertex has indegree and outdegree at least $k$ .

Conjecture For $d >2$ , every $d$ -diregular oriented graph on at most $4d+1$ vertices has a Hamilton cycle.

Keywords:

Posted by fhavet
updated March 8th, 2013

add new comment