25
votes
Accepted
Is the Robertson–Seymour theorem equivalent to the compactness of some topological space?
The Robertson–Seymour graph minor theorem states that the set of all (isomorphism classes of) finite undirected graphs under the graph minor relation is a well-quasi-ordering (or wqo for short). It ...
25
votes
Non-definability of graph 3-colorability in first-order logic
Here is one way to do it.
2-colorability case. First let's warm up with the 2-colorability case. Notice that odd-length cycles are not 2-colorable, since the colors have to alternate as you go around ...
21
votes
Brute force open problems in graph theory
The existence of a 57-regular "Moore graph" is one such problem.
We define the diameter of a graph $G$ to be the least $l$ such that any two vertices $u,v$ have a path between them using $\...
Community wiki
21
votes
Accepted
Parity and the Axiom of Choice
The Parity Principle follows from the axiom $\mathbf C_2$ (defined below) which is weaker than the Axiom of Choice. I don't know whether the Parity Principle implies $\mathbf C_2$, but that's another ...
18
votes
Accepted
Universal graph
I think that the answer is negative.
Assume that such graph $G$ on the vertex set $\{v_1,v_2,\ldots\}$ exists. We construct our not-embeddable graph $H$ on $\{1,2,\ldots\}$ by steps. On the $i$-th ...
16
votes
Who is M. Meyniel?
This "M. Meyniel" is indeed, and definitively, Henri Meyniel (sometimes spelled Henry Meyniel). Note that the article you mention was communicated by Berge, at a time (1972) when Meyniel was ...
16
votes
Brute force open problems in graph theory
Elaborating on the comment of Wojowu, for what positive integers $q$
does there exist a bipartite graph $G$ with vertex bipartition $(A,B)$
satisfying: (a) $|A|=|B|=q^2+q+1$, (b) $G$ is regular of ...
Community wiki
16
votes
Accepted
Connected graphs isomorphic to their own contraction
No. Let $G$ be the Rado graph (which is infinite, connected, and not complete), and $S$ a finite subset of the vertices of $G$ (because the Rado graph is countable). $G/S$ still has the extension ...
16
votes
Accepted
Scrambling a “Connections” grid
Yes, here is one solution for the 4-by-4 case found by a computer search. Each array is obtained from the previous one by applying the permutation (0 1 2 3 4)(5 6 7 8 9)(10 11 12 13 14) to the entries....
15
votes
Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$
This is false as shown by the following digraph.
From $x$ there is an edge to $v_p$, from $v_p$ there is a cycle of length $p$ to itself, and from $v_p$ there are $p-1$ different paths to $y$, of ...
15
votes
Could someone explain the proof of this formula clearly? I got the wrong values for spanning trees with this formula and with Cayley's formula
The problem is that for a complete graph, $\mu_{n-1} \leq \delta$ is wrong, and thus $f(\delta) < f(\mu_{n+1})$. This can be fixed by adding a special case for the complete graph (for other graphs $...
14
votes
Is End() a functor from the category of directed graphs to the category of monoids?
No, this isn’t possible. If $\newcommand{\End}{\mathrm{End}}\newcommand{\Aut}{\mathrm{Aut}}\End(-)$ extended to a functor on arbitrary maps of graphs, that would imply that whenever $G$ embeds as a ...
13
votes
Connected graphs isomorphic to their own contraction
No. Let $V = \mathbb{N}$ and $E = (0, i)$ for $i$ in $\mathbb{N}^*$ (a "star" graph where every vertex is connected to $0$).
If you collapse a subset containing $0$, the collapsed vertex can ...
12
votes
Brute force open problems in graph theory
Question: Does $K_{50}$ decompose into seven copies of the Hoffman-Singleton graph?
The following is copied from https://faculty.math.illinois.edu/~west/openp/hoffsing.html
Definitions: The Hoffman-...
Community wiki
12
votes
Does every big polyomino contain a big arithmetic progression?
Alternative proof to Zachs, with best bound: The answer is no, and the largest $k$ possible is $k=4$.
The proof is due to a theorem by Dekking from 1978:
There exists a sequence on two symbols in ...
11
votes
Accepted
Random sample of spanning trees
One approach is to generate $k$ random Prüfer sequences and then convert each sequence into a tree. It is also well-known that performing a random walk on $K_n$ will generate a random spanning tree ...
11
votes
A starting point for research in Graph Theory as a high schooler
I feel that you are asking two questions. (A) How to get started in research? and (B) What are some good books (for a high school student) in graph theory? Question (A) is in scope for mathoverflow, ...
Community wiki
10
votes
Postal code numbering adjacency problem
If there are four regions, three of which border the fourth but don't share a border with each other, then it's easy to see that there can't be any such numbering.
EDIT ––– I'm beginning to think this ...
10
votes
Accepted
Desargues ten point configuration $D_{10}$ in LaTeX
This example shows that $s\le 2$ and for this $s$, $c\le 3$.
Note that we are lucky with the latter, because there is a configuration for which every combinatorially equivalent realization has at ...
10
votes
Accepted
Is there an algorithm to generate graphs with given order and diameter?
About 58% of the graphs on 12 vertices have diameter 3, so filtering a complete generation will be as fast as any. On 20 vertices the fraction has dropped to about 31% but the total is so vast that ...
10
votes
Is there a bipartite graph with $\sqrt{2}$ as an eigenvalue with high multiplicity, specifically more than in the Heawood graph?
This is a limited partial answer to the question ruling out the case where the graph is regular and has four distinct eigenvalues, so the spectrum is $\{k, (\sqrt{2})^a, (-\sqrt{2})^a, -k\}$.
van Dam'...
10
votes
How to effectively search Internet for graphs not for function graphs?
Use Google Scholar instead of plain Google; I simply entered graphs and pretty much all the items returned by Google Scholar refer to graphs in the mathematical context.
It also suggests helpful ...
10
votes
Accepted
Generating 21-vertex 4-regular plane graphs with 8 faces of degree 3 and 15 faces of degree 4
Brinkmann and McKay's program plantri can generate planar quadrangulations, which are planar graphs with all faces of size 4.
If you generate these on 23 vertices ...
9
votes
Girth 5 graphs with diameter 2
No infinite family exists. In fact all graphs with diameter $d$ and girth $2d+1$ have to be regular, and thus are Moore graphs. This was proved in
R. Singleton, "There is no irregular Moore ...
9
votes
Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$
domotorp's lovely solution is by far the best one, but here is an explicit counterexample for $n = 10$, I wonder if it's computationally tractable to figure out the max $n$ for which your statement ...
9
votes
Two arcs in the complement of a disc must intersect?
Amplitwist's solution just with Jordan: Consider the curves on the Riemann sphere $S$ and connect $\pm 1$ along the real interval $R$ inside the disk such that $R \cup B$ is a closed curve on $S$. ...
9
votes
Accepted
Does every big polyomino contain a big arithmetic progression?
The answer is no. I will construct a connected subset $S\subset \Bbb{Z}^2$ without arbitrarily long arithmetic progressions. Since the grid is locally finite, $S$ must contain an infinite path $P\...
8
votes
Why $K_5$ and $K_{3,3}$?
I have now found a paper by A. Skopenkov where he proves the theorem from the fact that $K_5$ and $K_{3,3}$ are the only graphs $G$ with the property
For each edge $x y$, the Graph $G - x - y$ does ...
8
votes
Accepted
Probability of the random graph on $2n$ vertices having exactly $n$ vertices with degree $\ge n$
It certainly tends to $0$. The way to see it almost without any computation is to mark any $n$ disjoint edges. Then, when deciding the fate of the remaining edges, each vertex has $p=2^{2-2n}{2n-2\...
8
votes
Accepted
Isometric embeddings of metric $K_{n+1}$ in $\mathbb{R}^n$
With the $\ell_\infty$-norm this is true. For example, it is a classic theorem of Fréchet that every $n$-point metric space embeds in $\ell_\infty^{n-1}$. The required embedding $f$ is easy to define. ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
graph-theory × 5150co.combinatorics × 2232
graph-colorings × 524
reference-request × 446
algorithms × 337
pr.probability × 279
spectral-graph-theory × 266
random-graphs × 204
extremal-graph-theory × 198
gr.group-theory × 192
computational-complexity × 190
discrete-geometry × 175
linear-algebra × 173
mg.metric-geometry × 138
matching-theory × 124
combinatorial-optimization × 123
trees × 105
set-theory × 103
infinite-combinatorics × 103
hypergraph × 99
bipartite-graphs × 99
matrices × 96
perfect-matchings × 96
hamiltonian-graphs × 96
algebraic-graph-theory × 89