Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with graph-theory
Search options answers only
not deleted
user 1946
Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.
7
votes
Accepted
What determines internalization of graph-structures into the set world?
The answer is yes for equinumerosity (provided...), but no for graphs.
Equinumerosity. KM is commonly taken to include the axiom of choice and furthermore the axiom of global choice, and this makes th …
- 236k
3
votes
Does $(\omega, E)$ with the cycle condition have an $\omega$-path?
No. Draw edges from $0$ and $1$ to all numbers $n>1$. Now any two nodes lies on a cycle of length $4$. But there is no injective $\omega$-walk, since every edge touches either $0$ or $1$, and indeed e …
- 236k
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 …
- 236k
8
votes
Seymour's second neighborhood conjecture for infinite graphs
Allow me to make an observation concerning what I find to be an interesting angle on the question in the context without the axiom of choice, where there are competing conceptions of what it means to …
- 236k
9
votes
Accepted
A notion of thinness for subsets of $\omega$, using chromatic number
The two notions are incomparable.
To see that the first notion does not imply the second, let's construct a set $S$ with asymptotic density $0$, but with infinite chromatic number. We place infinitely …
- 236k
3
votes
Accepted
Is following function a metric on the set of isomorphism classes of graphs with countably ma...
To prove that this is a metric, consider the following theorem.
Theorem. If the second player can survive for $n$ steps in the $(\Gamma_1,\Gamma_2)$ game, and for $m$ steps in the $(\Gamma_2,\Gamma_3 …
- 236k
58
votes
Accepted
Does knight behave like a king in his infinite odyssey?
Consider the following open knight's tour on a $5\times 5$ board, starting at position $1$ and then touring the $5\times 5$ board in the indicated move order. The final position is $25$, from which th …
- 236k
5
votes
Graph of functions sharing a point
Gerhard has pointed out that your sharing-a-point graph is not universal for uncountable graphs, since any uncountable collection of functions on $\omega$ must have many of them sharing a point. So th …
- 236k
134
votes
What is a chess piece mathematically?
In terms of mathematical analysis and combinatorial game theory,
the essence of any game is captured by its game tree, the tree
whose nodes represent the current game state, and to make a move in
the …
- 236k
6
votes
Mutually non-isomorphic connected graphs on $\kappa$ points
The general fact is that every mathematical structure of size $\kappa$, in a language of size at most $\kappa$, can be coded as a (connected, undirected, simple) graph of size $\kappa$. What I mean is …
- 236k
4
votes
Applications of infinite graph theory
A model of set theory $\langle M,\in\rangle$ is a certain kind of directed graph. So graph theory has the capacity to serve as a foundation of mathematics, having a copy of virtually any conceivable m …
- 236k
3
votes
Accepted
Minimal coverings by maximal cliques
Nice question. The answer is no, not necessarily.
Theorem. There is a graph $G$ such that there is no minimal vertex
covering of it by maximal cliques. Indeed, in every vertex covering
$\cal C$ of $G …
- 236k
3
votes
Does the shortest distance between two cities of a Traveling Salesman Problem always appear ...
The answer is no.
Consider five cities, with $(a,b), (b,c), (c,d), (d,e)$ each having cost $2$, and $(b,d)$ cost $1$, but all other edges much more expensive. The shortest path visiting every city i …
- 236k
29
votes
Should axiomatic set theory be translated into graph theory?
Although it may seem on the face of it that this proposal is just a question of terminology — yes, a model of set theory is a certain kind of acyclic digraph — nevertheless, my opinion is that one can …
- 236k
9
votes
Accepted
Borel coloring of a graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$
I claim that there can be no Borel $\mathbb{N}$-coloring of this graph.
To see this, suppose toward contradiction that there is such a Borel coloring.
Consider the forcing to add a generic Cohen re …
- 236k