Home

Recent Activity

Analysis

$C^r$ Stability Conjecture ★★★★

Author(s): Palis; Smale

Conjecture   Any $ C^r $ structurally stable diffeomorphism is hyperbolic.

Keywords: diffeomorphisms,; dynamical systems

Posted by m n
updated December 20th, 2007
add new comment
Geometry

Convex 'Fair' Partitions Of Convex Polygons ★★

Author(s): Nandakumar; Ramana

Basic Question: Given any positive integer n, can any convex polygon be partitioned into n convex pieces so that all pieces have the same area and same perimeter?

Definitions: Define a Fair Partition of a polygon as a partition of it into a finite number of pieces so that every piece has both the same area and the same perimeter. Further, if all the resulting pieces are convex, call it a Convex Fair Partition.

Questions: 1. (Rephrasing the above 'basic' question) Given any positive integer n, can any convex polygon be convex fair partitioned into n pieces?

2. If the answer to the above is "Not always'', how does one decide the possibility of such a partition for a given convex polygon and a given n? And if fair convex partition is allowed by a specific convex polygon for a give n, how does one find the optimal convex fair partition that minimizes the total length of the cut segments?

3. Finally, what could one say about higher dimensional analogs of this question?

Conjecture: The authors tend to believe that the answer to the above 'basic' question is "yes". In other words they guess: Every convex polygon allows a convex fair partition into n pieces for any n

Keywords: Convex Polygons; Partitioning

Posted by Nandakumar
updated December 12th, 2007
add new comment
Group Theory

Growth of finitely presented groups ★★★

Author(s): Adyan

Problem   Does there exist a finitely presented group of intermediate growth?

Keywords: finitely presented; growth

Posted by mdevos
updated November 12th, 2007
add new comment
Combinatorics » Optimization

Ding's tau_r vs. tau conjecture ★★★

Author(s): Ding

Conjecture   Let $ r \ge 2 $ be an integer and let $ H $ be a minor minimal clutter with $ \frac{1}{r}\tau_r(H) < \tau(H) $. Then either $ H $ has a $ J_k $ minor for some $ k \ge 2 $ or $ H $ has Lehman's property.

Keywords: clutter; covering; MFMC property; packing

Posted by mdevos
updated November 11th, 2007
add new comment
Combinatorics » Matroid Theory

Equality in a matroidal circumference bound ★★

Author(s): Oxley; Royle

Question   Is the binary affine cube $ AG(3,2) $ the only 3-connected matroid for which equality holds in the bound $$E(M) \leq c(M) c(M^*) / 2$$ where $ c(M) $ is the circumference (i.e. largest circuit size) of $ M $?

Keywords: circumference

Posted by Gordon Royle
updated November 2nd, 2007
add new comment
Graph Theory » Infinite Graphs

Highly arc transitive two ended digraphs ★★

Author(s): Cameron; Praeger; Wormald

Conjecture   If $ G $ is a highly arc transitive digraph with two ends, then every tile of $ G $ is a disjoint union of complete bipartite graphs.

Keywords: arc transitive; digraph; infinite graph

Posted by mdevos
updated October 29th, 2007
add new comment
Graph Theory » Infinite Graphs

Strong matchings and covers ★★★

Author(s): Aharoni

Let $ H $ be a hypergraph. A strongly maximal matching is a matching $ F \subseteq E(H) $ so that $ |F' \setminus F| \le |F \setminus F'| $ for every matching $ F' $. A strongly minimal cover is a (vertex) cover $ X \subseteq V(H) $ so that $ |X' \setminus X| \ge |X \setminus X'| $ for every cover $ X' $.

Conjecture   If $ H $ is a (possibly infinite) hypergraph in which all edges have size $ \le k $ for some integer $ k $, then $ H $ has a strongly maximal matching and a strongly minimal cover.

Keywords: cover; infinite graph; matching

Posted by mdevos
updated October 23rd, 2007
add new comment
Graph Theory » Infinite Graphs

Unfriendly partitions ★★★

Author(s): Cowan; Emerson

If $ G $ is a graph, we say that a partition of $ V(G) $ is unfriendly if every vertex has at least as many neighbors in the other classes as in its own.

Problem   Does every countably infinite graph have an unfriendly partition into two sets?

Keywords: coloring; infinite graph; partition

Posted by mdevos
updated October 22nd, 2007
add new comment
Graph Theory » Infinite Graphs

Universal highly arc transitive digraphs ★★★

Author(s): Cameron; Praeger; Wormald

An alternating walk in a digraph is a walk $ v_0,e_1,v_1,\ldots,v_m $ so that the vertex $ v_i $ is either the head of both $ e_i $ and $ e_{i+1} $ or the tail of both $ e_i $ and $ e_{i+1} $ for every $ 1 \le i \le m-1 $. A digraph is universal if for every pair of edges $ e,f $, there is an alternating walk containing both $ e $ and $ f $

Question   Does there exist a locally finite highly arc transitive digraph which is universal?

Keywords: arc transitive; digraph

Posted by mdevos
updated October 21st, 2007
add new comment
Theoretical Comp. Sci. » Algorithms

P vs. NP ★★★★

Author(s): Cook; Levin

Problem   Is P = NP?

Keywords: Complexity Class; Computational Complexity; Millenium Problems; NP; P; polynomial algorithm

Posted by zitterbewegung
updated October 18th, 2007
add new comment
Logic

F_d versus F_{d+1} ★★★

Author(s): Krajicek

Problem   Find a constant $ k $ such that for any $ d $ there is a sequence of tautologies of depth $ k $ that have polynomial (or quasi-polynomial) size proofs in depth $ d+1 $ Frege system $ F_{d+1} $ but requires exponential size $ F_d $ proofs.

Keywords: Frege system; short proof

Posted by zitterbewegung
updated October 18th, 2007
add new comment
Combinatorics

Even vs. odd latin squares ★★★

Author(s): Alon; Tarsi

A latin square is even if the product of the signs of all of the row and column permutations is 1 and is odd otherwise.

Conjecture   For every positive even integer $ n $, the number of even latin squares of order $ n $ and the number of odd latin squares of order $ n $ are different.

Keywords: latin square

Posted by mdevos
updated October 7th, 2007
add new comment
Graph Theory » Coloring » Edge coloring

Universal Steiner triple systems ★★

Author(s): Grannell; Griggs; Knor; Skoviera

Problem   Which Steiner triple systems are universal?

Keywords: cubic graph; Steiner triple system

Posted by macajova
updated October 5th, 2007
add new comment
Combinatorics

Monotone 4-term Arithmetic Progressions ★★

Author(s): Davis; Entringer; Graham; Simmons

Question   Is it true that every permutation of positive integers must contain monotone 4-term arithmetic progressions?

Keywords: monotone arithmetic progression; permutation

Posted by vjungic
updated October 3rd, 2007
add new comment
Graph Theory » Directed Graphs

The Bermond-Thomassen Conjecture ★★

Author(s): Bermond; Thomassen

Conjecture   For every positive integer $ k $, every digraph with minimum out-degree at least $ 2k-1 $ contains $ k $ disjoint cycles.

Keywords: cycles

Posted by JS
updated October 1st, 2007
add new comment
Geometry » Polytopes

Continous analogue of Hirsch conjecture ★★

Author(s): Deza; Terlaky; Zinchenko

Conjecture   The order of the largest total curvature of the primal central path over all polytopes defined by $ n $ inequalities in dimension $ d $ is $ n $.

Keywords: curvature; polytope

Posted by deza
updated September 30th, 2007
add new comment
Geometry

Average diameter of a bounded cell of a simple arrangement ★★

Author(s): Deza; Terlaky; Zinchenko

Conjecture   The average diameter of a bounded cell of a simple arrangement defined by $ n $ hyperplanes in dimension $ d $ is not greater than $ d $.

Keywords: arrangement; diameter; polytope

Posted by deza
updated September 30th, 2007
add new comment
Graph Theory » Topological G.T. » Crossing numbers

Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

Conjecture   Let $ G $ be the disjoint union of the graphs $ G_1 $ and $ G_2 $ and let $ \Sigma $ be a surface. Is it true that every optimal drawing of $ G $ on $ \Sigma $ has the property that $ G_1 $ and $ G_2 $ are disjoint?

Keywords: crossing number; surface

Posted by mdevos
updated September 30th, 2007
1 comment
Graph Theory » Basic G.T. » Matchings

Matchings extend to Hamiltonian cycles in hypercubes ★★

Author(s): Ruskey; Savage

Question   Does every matching of hypercube extend to a Hamiltonian cycle?

Keywords: Hamiltonian cycle; hypercube; matching

Posted by Jirka
updated September 28th, 2007
add new comment
Graph Theory » Topological G.T. » Drawings

Linear Hypergraphs with Dimension 3 ★★

Author(s): de Fraysseix; Ossona de Mendez; Rosenstiehl

Conjecture   Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.

Keywords: Hypergraphs

Posted by taxipom
updated September 26th, 2007
add new comment