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.
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
72
votes
Can a problem be simultaneously polynomial time and undecidable?
Consider the following simplified example of the same phenomenon, which many students find clarifying.
Let $f(n)=1$, if there are $n$ consecutive $7$s in the decimal expansion of $\pi$, and otherwise …
- 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
31
votes
Which graphs are Cayley graphs?
I've managed to answer a few of the latter questions, and please look below for a solution in the finite-degree case.
Theorem. There is an uncountable graph $\Gamma$ that is not a Cayley graph in …
- 236k
30
votes
Accepted
Human checkable proof of the Four Color Theorem?
This is too long for a comment, so I am placing it here.
In this article of the Notices of the AMS, Gonthier describes a full formal proof of the four-color theorem, which makes explicit every logica …
- 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
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
19
votes
What are some good examples of non-monotone graph properties?
There are a large number of natural graph properties that are not monotone.
The property of being isomorphic to a given graph is never monotone (except for the empty graph and the complete graph). …
- 236k
11
votes
Accepted
Is non-connectedness of graphs first order axiomatizable?
Stefan's original idea is realized in the following observation, which shows that one $\mathbb{Z}$-chain is elementary equivalent to two such chains.
Theorem. The theory of nontrivial cycle-free grap …
- 236k
11
votes
How are Modal Logic and Graph Theory related?
The ability of modal assertions to define natural and interesting
classes of frames (or digraphs) is indeed intensely studied and
constitutes one of the principal perpsectives of the subject,
pervasiv …
- 236k
9
votes
Accepted
Characterization of transitive closure graphs
There are a few problems with what you wrote.
First, you probably want $TC(\{X\})$ rather than $TC(X)$, since you want $X$ to be an element, not just a subset, since it is the node corresponding t …
- 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
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
8
votes
Accepted
A distinguishing node property in trees?
I have a counterexample. It is not enough just to count leaves, since this doesn't take into account the number of possible ways to arrive at those leaves.
Consider the graph below.
A - B - C - …
- 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