# Recent Activity

## Characterizing (aleph_0,aleph_1)-graphs ★★★

Call a graph an -*graph* if it has a bipartition so that every vertex in has degree and every vertex in has degree .

**Problem**Characterize the -graphs.

Keywords: binary tree; infinite graph; normal spanning tree; set theory

## The Berge-Fulkerson conjecture ★★★★

**Conjecture**If is a bridgeless cubic graph, then there exist 6 perfect matchings of with the property that every edge of is contained in exactly two of .

Keywords: cubic; perfect matching

## Obstacle number of planar graphs ★

Author(s): Alpert; Koch; Laison

Does there exist a planar graph with obstacle number greater than 1? Is there some such that every planar graph has obstacle number at most ?

Keywords: graph drawing; obstacle number; planar graph; visibility graph

## Twin prime conjecture ★★★★

Author(s):

**Conjecture**There exist infinitely many positive integers so that both and are prime.

Keywords: prime; twin prime

## Square achievement game on an n x n grid ★★

Author(s): Erickson

**Problem**Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an grid. The first player (if any) to occupy four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play? Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15.

Keywords: game

## What is the largest graph of positive curvature? ★

**Problem**What is the largest connected planar graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism or antiprism?

Keywords: curvature; planar graph

## Extension complexity of (convex) polygons ★★

Author(s):

The extension complexity of a polytope is the minimum number for which there exists a polytope with facets and an affine mapping with .

**Question**Does there exists, for infinitely many integers , a convex polygon on vertices whose extension complexity is ?

Keywords: polytope, projection, extension complexity, convex polygon

## Strict inequalities for products of filters ★

Author(s): Porton

**Conjecture**for some filter objects , . Particularly, is this formula true for ?

A weaker conjecture:

**Conjecture**for some filter objects , .

Keywords: filter products

## Barnette's Conjecture ★★★

Author(s): Barnette

**Conjecture**Every 3-connected cubic planar bipartite graph is Hamiltonian.

Keywords: bipartite; cubic; hamiltonian

## Covering a square with unit squares ★★

Author(s):

**Conjecture**For any integer , it is impossible to cover a square of side greater than with unit squares.

Keywords:

## Sequence defined on multisets ★★

Author(s): Erickson

**Conjecture**Define a array of positive integers where the first row consists of some distinct positive integers arranged in increasing order, and the second row consists of any positive integers in any order. Create a new array where the first row consists of all the integers that occur in the first array, arranged in increasing order, and the second row consists of their multiplicities. Repeat the process. For example, starting with the array , the sequence is: -> -> -> -> -> -> -> -> -> -> -> , and we now have a fixed point (loop of one array).

The process always results in a loop of 1, 2, or 3 arrays.

## Vertex Coloring of graph fractional powers ★★★

Author(s): Iradmusa

**Conjecture**Let be a graph and be a positive integer. The

*power of*, denoted by , is defined on the vertex set , by connecting any two distinct vertices and with distance at most . In other words, . Also

*subdivision of*, denoted by , is constructed by replacing each edge of with a path of length . Note that for , we have .

Now we can define the fractional power of a graph as follows:

Let be a graph and . The graph is defined by the power of the subdivision of . In other words .

*Conjecture.*Let be a connected graph with and be a positive integer greater than 1. Then for any positive integer , we have .

In [1], it was shown that this conjecture is true in some special cases.

Keywords: chromatic number, fractional power of graph, clique number

## Covering powers of cycles with equivalence subgraphs ★

Author(s):

**Conjecture**Given and , the graph has equivalence covering number .

Keywords:

## Complexity of square-root sum ★★

Author(s): Goemans

**Question**What is the complexity of the following problem?

Given , determine whether or not

Keywords: semi-definite programming

## Snevily's conjecture ★★★

Author(s): Snevily

**Conjecture**Let be an abelian group of odd order and let satisfy . Then the elements of and may be ordered and so that the sums are pairwise distinct.

Keywords: addition table; latin square; transversal

## Invariant subspace problem ★★★

Author(s):

**Problem**Does every bounded linear operator on an infinite-dimensional separable Hilbert space have a non-trivial closed invariant subspace?

Keywords: subspace

## Sets with distinct subset sums ★★★

Author(s): Erdos

Say that a set has *distinct subset sums* if distinct subsets of have distinct sums.

**Conjecture**There exists a fixed constant so that whenever has distinct subset sums.

Keywords: subset sum