# Random

## Which compact boundaryless 3-manifolds embed smoothly in the 4-sphere? ★★★

Author(s): Kirby

**Problem**Determine a computable set of invariants that allow one to determine, given a compact boundaryless 3-manifold, whether or not it embeds smoothly in the 4-sphere. This should include a constructive procedure to find an embedding if the manifold is embeddable.

Keywords: 3-manifold; 4-sphere; embedding

## Finite entailment of Positive Horn logic ★★

Author(s): Martin

**Question**Positive Horn logic (pH) is the fragment of FO involving exactly . Does the fragment have the finite model property?

Keywords: entailment; finite satisfiability; horn logic

## The intersection of two perfect matchings ★★

**Conjecture**Every bridgeless cubic graph has two perfect matchings , so that does not contain an odd edge-cut.

Keywords: cubic; nowhere-zero flow; perfect matching

## Decomposing an eulerian graph into cycles. ★★

Author(s): Hajós

**Conjecture**Every simple eulerian graph on vertices can be decomposed into at most cycles.

Keywords:

## Graham's conjecture on tree reconstruction ★★

Author(s): Graham

**Problem**for every graph , we let denote the line graph of . Given that is a tree, can we determine it from the integer sequence ?

Keywords: reconstruction; tree

## Another conjecture about reloids and funcoids ★★

Author(s): Porton

**Definition**for reloid .

**Conjecture**for every funcoid .

Note: it is known that (see below mentioned online article).

Keywords:

## Rainbow AP(4) in an almost equinumerous coloring ★★

Author(s): Conlon

**Problem**Do 4-colorings of , for a large prime, always contain a rainbow if each of the color classes is of size of either or ?

Keywords: arithmetic progression; rainbow

## Imbalance conjecture ★★

Author(s): Kozerenko

**Conjecture**Suppose that for all edges we have . Then is graphic.

Keywords: edge imbalance; graphic sequences

## Diagonal Ramsey numbers ★★★★

Author(s): Erdos

Let denote the diagonal Ramsey number.

**Conjecture**exists.

**Problem**Determine the limit in the above conjecture (assuming it exists).

Keywords: Ramsey number

## Infinite distributivity of meet over join for a principal funcoid ★★

Author(s): Porton

**Conjecture**for principal funcoid and a set of funcoids of appropriate sources and destinations.

Keywords: distributivity; principal funcoid

## Matchings extend to Hamiltonian cycles in hypercubes ★★

Keywords: Hamiltonian cycle; hypercube; matching

## A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

**Conjecture**Let be integers. Set and for . Eventually we have ; put .

Example: , since , , , , , , , .

Prove or disprove: .

Keywords: Pierce expansions

## Hamiltonian cycles in line graphs of infinite graphs ★★

Author(s): Georgakopoulos

**Conjecture**

- \item If is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. \item If the line graph of a locally finite graph is 4-connected, then is hamiltonian.

Keywords: hamiltonian; infinite graph; line graphs

## Do any three longest paths in a connected graph have a vertex in common? ★★

Author(s): Gallai

**Conjecture**Do any three longest paths in a connected graph have a vertex in common?

Keywords:

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

## The Bermond-Thomassen Conjecture ★★

**Conjecture**For every positive integer , every digraph with minimum out-degree at least contains disjoint cycles.

Keywords: cycles

## Fat 4-polytopes ★★★

Author(s): Eppstein; Kuperberg; Ziegler

The *fatness* of a 4-polytope is defined to be where is the number of faces of of dimension .

**Question**Does there exist a fixed constant so that every convex 4-polytope has fatness at most ?

## A funcoid related to directed topological spaces ★★

Author(s): Porton

**Conjecture**Let be the complete funcoid corresponding to the usual topology on extended real line . Let be the order on this set. Then is a complete funcoid.

**Proposition**It is easy to prove that is the infinitely small right neighborhood filter of point .

If proved true, the conjecture then can be generalized to a wider class of posets.

Keywords:

## trace inequality ★★

Author(s):

Let be positive semidefinite, by Jensen's inequality, it is easy to see , whenever .

What about the , is it still valid?

Keywords:

## Long directed cycles in diregular digraphs ★★★

Author(s): Jackson

**Conjecture**Every strong oriented graph in which each vertex has indegree and outdegree at least contains a directed cycle of length at least .

Keywords:

## Are there infinite number of Mersenne Primes? ★★★★

Author(s):

**Conjecture**A Mersenne prime is a Mersenne number that is prime.

Are there infinite number of Mersenne Primes?

Keywords: Mersenne number; Mersenne prime

## Domination in cubic graphs ★★

Author(s): Reed

**Problem**Does every 3-connected cubic graph satisfy ?

Keywords: cubic graph; domination

## Outer reloid of restricted funcoid ★★

Author(s): Porton

**Question**for every filter objects and and a funcoid ?

Keywords: direct product of filters; outer reloid

## Erdős-Posa property for long directed cycles ★★

**Conjecture**Let be an integer. For every integer , there exists an integer such that for every digraph , either has a pairwise-disjoint directed cycles of length at least , or there exists a set of at most vertices such that has no directed cycles of length at least .

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

## Monochromatic empty triangles ★★★

Author(s):

If is a finite set of points which is 2-colored, an *empty triangle* is a set with so that the convex hull of is disjoint from . We say that is *monochromatic* if all points in are the same color.

**Conjecture**There exists a fixed constant with the following property. If is a set of points in general position which is 2-colored, then it has monochromatic empty triangles.

Keywords: empty triangle; general position; ramsey theory

## Almost all non-Hamiltonian 3-regular graphs are 1-connected ★★

Author(s): Haythorpe

**Conjecture**Denote by the number of non-Hamiltonian 3-regular graphs of size , and similarly denote by the number of non-Hamiltonian 3-regular 1-connected graphs of size .

Is it true that ?

## Hamilton cycle in small d-diregular graphs ★★

Author(s): Jackson

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

**Conjecture**For , every -diregular oriented graph on at most vertices has a Hamilton cycle.

Keywords:

## Aharoni-Berger conjecture ★★★

**Conjecture**If are matroids on and for every partition of , then there exists with which is independent in every .

Keywords: independent set; matroid; partition

## Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph is -*degenerate* if every subgraph of has a vertex of degree .

**Conjecture**Every simple planar graph has a 5-coloring so that for , the union of any color classes induces a -degenerate graph.

Keywords: coloring; degenerate; planar

## Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour. ★★

Author(s): Sabidussi

**Conjecture**Let be an eulerian graph of minimum degree , and let be an eulerian tour of . Then admits a decomposition into cycles none of which contains two consecutive edges of .

Keywords:

## Erdős–Faber–Lovász conjecture ★★★

Author(s): Erdos; Faber; Lovasz

**Conjecture**If is a simple graph which is the union of pairwise edge-disjoint complete graphs, each of which has vertices, then the chromatic number of is .

Keywords: chromatic number

## Real roots of the flow polynomial ★★

Author(s): Welsh

**Conjecture**All real roots of nonzero flow polynomials are at most 4.

Keywords: flow polynomial; nowhere-zero flow

## Roller Coaster permutations ★★★

Let denote the set of all permutations of . Let and denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in . Let denote the set of subsequences of with length at least three. Let denote .

A permutation is called a *Roller Coaster permutation* if . Let be the set of all Roller Coaster permutations in .

**Conjecture**For ,

- \item If , then . \item If , then with .

**Conjecture (Odd Sum conjecture)**Given ,

- \item If , then is odd for . \item If , then for all .

Keywords:

## Dividing up the unrestricted partitions ★★

Begin with the generating function for unrestricted partitions:

(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...

Now change some of the plus signs to minus signs. The resulting series will have coefficients congruent, mod 2, to the coefficients of the generating series for unrestricted partitions. I conjecture that the signs may be chosen such that all the coefficients of the series are either 1, -1, or zero.

Keywords: congruence properties; partition

## Direct proof of a theorem about compact funcoids ★★

Author(s): Porton

**Conjecture**Let is a -separable (the same as for symmetric transitive) compact funcoid and is a uniform space (reflexive, symmetric, and transitive endoreloid) such that . Then .

The main purpose here is to find a *direct* proof of this conjecture. It seems that this conjecture can be derived from the well known theorem about existence of exactly one uniformity on a compact set. But that would be what I call an indirect proof, we need a direct proof instead.

The direct proof may be constructed by correcting all errors an omissions in this draft article.

Direct proof could be better because with it we would get a little more general statement like this:

**Conjecture**Let be a -separable compact reflexive symmetric funcoid and be a reloid such that

- \item ; \item .

Then .

Keywords: compact space; compact topology; funcoid; reloid; uniform space; uniformity

## Antidirected trees in digraphs ★★

Author(s): Addario-Berry; Havet; Linhares Sales; Reed; Thomassé

An antidirected tree is an orientation of a tree in which every vertex has either indegree 0 or outdergree 0.

**Conjecture**Let be a digraph. If , then contains every antidirected tree of order .

Keywords:

## Inverse Galois Problem ★★★★

Author(s): Hilbert

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

Keywords:

## Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

**Conjecture**Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?

Keywords: crossing number; surface

## Odd incongruent covering systems ★★★

**Conjecture**There is no covering system whose moduli are odd, distinct, and greater than 1.

Keywords: covering system

## Algebraic independence of pi and e ★★★

Author(s):

**Conjecture**and are algebraically independent

Keywords: algebraic independence

## Forcing a $K_6$-minor ★★

Author(s): Barát ; Joret; Wood

**Conjecture**Every graph with minimum degree at least 7 contains a -minor.

**Conjecture**Every 7-connected graph contains a -minor.

Keywords: connectivity; graph minors

## Perfect 2-error-correcting codes over arbitrary finite alphabets. ★★

Author(s):

**Conjecture**Does there exist a nontrivial perfect 2-error-correcting code over any finite alphabet, other than the ternary Golay code?

Keywords: 2-error-correcting; code; existence; perfect; perfect code

## Are there only finite Fermat Primes? ★★★

Author(s):

**Conjecture**A Fermat prime is a Fermat number that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.

Keywords:

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

## Sum of prime and semiprime conjecture ★★

Author(s): Geoffrey Marnell

**Conjecture**Every even number greater than can be represented as the sum of an odd prime number and an odd semiprime .

## Turán Problem for $10$-Cycles in the Hypercube ★★

Author(s): Erdos

**Problem**Bound the extremal number of in the hypercube.

Keywords: cycles; extremal combinatorics; hypercube

## Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set is -*universal* if every vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in , and all edges are (non-intersecting) straight line segments.

**Question**Does there exist an -universal set of size ?

Keywords: geometric graph; planar graph; universal set

## 2-colouring a graph without a monochromatic maximum clique ★★

**Conjecture**If is a non-empty graph containing no induced odd cycle of length at least , then there is a -vertex colouring of in which no maximum clique is monochromatic.

Keywords: maximum clique; Partitioning