Mathematics Problem Archive

Problem Determine $\text{wsat}(K_n,Q_3)$....

Conjecture For every fixed $k\geq2$ and fixed colouring $\chi$ of $E(K_k)$ with $m$ colours, there exists $\varepsilon>0$ such that every colouring of...

Setup Fix a tree $T$ and for every vertex $v \in V(T)$ a non-negative integer $g(v)$ which we think of as the amount of gold at $v$. 2-Player game Pl...

Question Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?...

Conjecture Let $H$ be an $r$-uniform $r$-partite hypergraph. If $\nu$ is the maximum number of pairwise disjoint edges in $H$, and $\tau$ is the size ...

Conjecture Let $H$ be a $k$-uniform hypergraph. If $H$ is a critical $k$-forest, then it is a $k$-tree....

Conjecture Let $F$ be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists $x$ such that $x$ is an ele...

Problem Let $H_1$ and $H_2$ be two $r$-uniform hypergraph on the same vertex set $V$. Does there always exist a partition of $V$ into $r$ classes $V_1...

Conjecture Every simple $3$-uniform hypergraph on $3n$ vertices which contains no complete $3$-uniform hypergraph on four vertices has at most $\frac1...

Conjecture Every infinite graph is a proper minor of itself....

Problem Does there exist a graph with no subgraph isomorphic to $K_4$ which cannot be expressed as a union of $\aleph_0$ triangle free graphs?...

Problem Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree $r > 2$?...

Conjecture - If $G$ is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. - If the line graph $L(G)$ of a locally finite gr...

Conjecture - If $G$ is a countable connected graph then its third power is hamiltonian. - If $G$ is a 2-connected countable graph then its square is ...

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 tai...

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

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 matchi...

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

Problem Let $G$ be a graph, $\omega$ a countable end of $G$, and $K$ an infinite set of pairwise disjoint $\omega$-rays in $G$. Prove that there is a ...

Call a graph an $(\aleph_0,\aleph_1)$-graph if it has a bipartition $(A,B)$ so that every vertex in $A$ has degree $\aleph_0$ and every vertex in $B$ ...

If $G$ is a graph and $p \in [0,1]$, we let $G_p$ denote a subgraph of $G$ where each edge of $G$ appears in $G_p$ with independently with probability...

Conjecture Let $G$ be a finite graph, let $e,f \in E(G)$, and let $F$ be the edge set of a forest chosen uniformly at random from all forests of $G$. ...

Question Is the chromatic number of a random lift of $K_5$ concentrated on a single value?...

Conjecture Every sufficiently large plane triangulation $G$ has a dominating set of size $\le \frac{1}{4} |V(G)|$....

Conjecture Every planar graph on $n$ verices has an induced forest with at least $n/2$ vertices....

Conjecture Every 4-connected toroidal graph has a Hamilton cycle....

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

Conjecture There exists a fixed constant $c$ (probably $c=4$ suffices) so that every embedded (loopless) graph with edge-width $\ge c$ has a 5-local-t...

A graph $G$ is $k$-degenerate if every subgraph of $G$ has a vertex of degree $\le k$. Conjecture Every simple planar graph has a 5-coloring so that ...

Consider a set $S$ of great circles on a sphere with no three circles meeting at a point. The arrangement graph of $S$ has a vertex for each intersect...

The crossing number $cr(G)$ of $G$ is the minimum number of crossings in all drawings of $G$ in the plane. Conjecture $\displaystyle cr(K_n) = \frac ...

The crossing number $cr(G)$ of $G$ is the minimum number of crossings in all drawings of $G$ in the plane. Conjecture $\displaystyle cr(K_{m,n}) = \f...

The crossing number $cr(G)$ of $G$ is the minimum number of crossings in all drawings of $G$ in the plane. The $d$-dimensional (hyper)cube $Q_d$ is t...

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

Conjecture Let $(a_0,a_1,a_2,\ldots,0)$ be a sequence of nonnegative integers which strictly decreases until $0$. Then there exists a graph that be d...

We let $cr(G)$ denote the crossing number of a graph $G$. Conjecture Every graph $G$ with $\chi(G) \ge t$ satisfies $cr(G) \ge cr(K_t)$....

Problem Does the following equality hold for every graph $G$? $$ \text{pair-cr}(G) = \text{cr}(G) $$ The crossing number $\text{cr}(G)$ of a graph $G...

We say that a set $P \subseteq {\mathbb R}^2$ is $n$-universal if every $n$ vertex planar graph can be drawn in the plane so that each vertex maps to ...

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

Conjecture Is there a graph $G$ that is a minor-minimal obstruction for two non-orientable surfaces?...

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

Can the sequence of metric balls in an infinite Cayley graph form a family of expanders?...

For a graph sequence $(G_n)$ define $e((G_n))=\liminf |E(G_n)|/|V(G_n)|$, and define its combinatorial cost as the infimum of $e((H_n))$ over graph se...

Compactness implies that for every $\varepsilon>0$ there is $K>0$ such that every finite graph can be approximated within error $\varepsilon$ by a fin...

Which probability measures can occur as eigenvalue distributions of finite $d$-regular graphs? Find natural restrictions....

Do uniformly random $d$-regular graphs converge, in local-global convergence, to the weak closure of independent identically distributed processes?...

Is the i.i.d. action of the free group $F_2$ a local-global limit of finite actions of $F_2$?...

Can every ergodic unimodular random network that is almost surely an infinite tree be obtained as the limit of an expander family?...

Let $G$ be an infinite vertex-transitive graph, let $A$ be a finite vertex set, let $b$ be a vertex, and let $\partial A$ be the set of vertices at di...

Define the first $L^2$ Betti number of a vertex-transitive graph $G$ from the expected degree of a free spanning forest. Do $G$ and its square $G^2$ h...