Recent Activity

Distribution and upper bound of mimic numbers ★★

Author(s): Bhattacharyya

Problem

Let the notation denote '' divides ''. The mimic function in number theory is defined as follows [1].

Definition   For any positive integer divisible by , the mimic function, , is given by,

By using this definition of mimic function, the mimic number of any non-prime integer is defined as follows [1].

Definition   The number is defined to be the mimic number of any positive integer , with respect to , for the minimum value of which .

Given these two definitions and a positive integer , find the distribution of mimic numbers of those numbers divisible by .

Again, find whether there is an upper bound of mimic numbers for a set of numbers divisible by any fixed positive integer .

Keywords: Divisibility; mimic function; mimic number

Coloring random subgraphs ★★

Author(s): Bukh

If is a graph and , we let denote a subgraph of where each edge of appears in with independently with probability .

Problem   Does there exist a constant so that ?

Keywords: coloring; random graph

Are vertex minor closed classes chi-bounded? ★★

Author(s): Geelen

Question   Is every proper vertex-minor closed class of graphs chi-bounded?

Keywords: chi-bounded; circle graph; coloring; vertex minor

Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family of graphs is -bounded if there exists a function so that every satisfies .

Conjecture   For every fixed tree , the family of graphs with no induced subgraph isomorphic to is -bounded.

Keywords: chi-bounded; coloring; excluded subgraph; tree

Asymptotic Distribution of Form of Polyhedra ★★

Author(s): Rüdinger

Problem   Consider the set of all topologically inequivalent polyhedra with edges. Define a form parameter for a polyhedron as where is the number of vertices. What is the distribution of for ?

Keywords: polyhedral graphs, distribution

Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

Conjecture   Every sufficiently large plane triangulation has a dominating set of size .

Keywords: coloring; domination; multigrid; planar graph; triangulation

Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

Conjecture   A triangle-free graph with maximum degree has chromatic number at most .

Keywords: chromatic number; girth; maximum degree; triangle free

Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

Conjecture   Every set of points in the plane in general position contains a subset of points which form a convex -gon.

4-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow.

Keywords: minor; nowhere-zero flow; Petersen graph

Inequality of the means ★★★

Author(s):

Question   Is is possible to pack rectangular -dimensional boxes each of which has side lengths inside an -dimensional cube with side length ?

Keywords: arithmetic mean; geometric mean; Inequality; packing

P vs. PSPACE ★★★

Author(s): Folklore

Problem   Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE?

Keywords: P; PSPACE; separation; unconditional

Sums of independent random variables with unbounded variance ★★

Author(s): Feige

Conjecture   If are independent random variables with , then

Grunbaum's Conjecture ★★★

Author(s): Grunbaum

Conjecture   If is a simple loopless triangulation of an orientable surface, then the dual of is 3-edge-colorable.

Keywords: coloring; surface

Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★

Author(s): Feige

Conjecture   For every rational and every rational , there is no polynomial-time algorithm for the following problem.

Given is a 3SAT (3CNF) formula on variables, for some , and clauses drawn uniformly at random from the set of formulas on variables. Return with probability at least 0.5 (over the instances) that is typical without returning typical for any instance with at least simultaneously satisfiable clauses.

Keywords: NP; randomness in TCS; satisfiability

Does the chromatic symmetric function distinguish between trees? ★★

Author(s): Stanley

Problem   Do there exist non-isomorphic trees which have the same chromatic symmetric function?

Keywords: chromatic polynomial; symmetric function; tree

Shannon capacity of the seven-cycle ★★★

Author(s):

Problem   What is the Shannon capacity of ?

Keywords:

Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let be a finite undirected simple graph.

A -page book embedding of consists of a linear order of and a (non-proper) -colouring of such that edges with the same colour do not cross with respect to . That is, if for some edges , then and receive distinct colours.

One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.

The book thickness of , denoted by bt is the minimum integer for which there is a -page book embedding of .

Let be the graph obtained by subdividing each edge of exactly once.

Conjecture   There is a function such that for every graph ,

Keywords: book embedding; book thickness

Frobenius number of four or more integers ★★

Author(s):

Problem   Find an explicit formula for Frobenius number of co-prime positive integers for .

Keywords:

Magic square of squares ★★

Author(s): LaBar

Question   Does there exist a magic square composed of distinct perfect squares?

Keywords:

Diophantine quintuple conjecture ★★

Author(s):

Definition   A set of m positive integers is called a Diophantine -tuple if is a perfect square for all .
Conjecture  (1)   Diophantine quintuple does not exist.

It would follow from the following stronger conjecture [Da]:

Conjecture  (2)   If is a Diophantine quadruple and , then

Keywords: