# 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

## 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:

## 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:

## Inverse Galois Problem ★★★★

Author(s): Hilbert

Conjecture   Every finite group is the Galois group of some finite algebraic extension of .

Keywords:

## Seymour's r-graph conjecture ★★★

Author(s): Seymour

An -graph is an -regular graph with the property that for every with odd size.

Conjecture   for every -graph .

Keywords: edge-coloring; r-graph

## Edge list coloring conjecture ★★★

Author(s):

Conjecture   Let be a loopless multigraph. Then the edge chromatic number of equals the list edge chromatic number of .

Keywords: