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 not deleted
user 160416
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.
5
votes
Accepted
Graphs on $\{0,1\}^n$ based on fixed Hamming distance
In general, this is an open problem. In the special case where $n$ is divisible by $4$ and $k=n/2$, the clique number is believed to be $n$ but this is equivalent to the Hadamard matrix conjecture. I …
- 3,446
4
votes
0
answers
103
views
Maximal number of smallest circuits in a matroid
It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$.
Since this can be be ph …
- 3,446
3
votes
1
answer
190
views
Discrepancy of random bipartite graphs
This is a crosspost from MathStackExchange (original question).
Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$).
Define a rando …
- 3,446
3
votes
1
answer
332
views
Can graphs of groups be thought of as "graph objects" in the category of groupoids?
An undirected graph is sometimes defined as a pair of sets $V$ and $E$ (vertices and oriented edges), together with two maps $i,f: E\to V$ (sending a directed edge its initial/final vertex) and a map …
- 3,446
2
votes
Squaring a square and discrete Ricci flow
I don't know about having one vertex per square, but there is a similar very interesting construction with edges at squares. It does not answer your question but it will still surely interest you.
Spe …
- 3,446
2
votes
Accepted
Probability calculation of rooted trees
We can see any tree $T$ as the Hasse diagram of a poset whose smallest element is the root. I will freely identify the tree with the corresponding poset.
If we label by $i$ the $i$'th vertex added in …
- 3,446
2
votes
Existence of certain regular graphs
Take the graph on $2k+2$ vertices $x_0, \ldots, x_k, y_0, \ldots, y_k$ with an edge between any pair of distinct vertices except $(x_i, y_i)$ for $0\le i \le k$. There are plenty of $2$-factors, e.g. …
- 3,446
1
vote
Accepted
Oriented path in a graph
With the acyclic condition, the answer is yes. Starting at $v$ and repeatedly following any edge exiting the current vertex, you will eventually end up at $t$, by acyclicity and uniqueness of the sink …
- 3,446
1
vote
1
answer
150
views
Discrepancy of random bipartite graphs (2)
This question is a modification of the one asked here, which turned out to ask for something too strong to be true.
Given $k>0$ and a positive integer $n$, let $X, Y$ be two vertex sets of size $n$ an …
- 3,446
1
vote
Accepted
Discrepancy of random bipartite graphs (2)
The answer is yes, and the union bound actually does work.
By applying the multiplicative Chernoff bound found here with $\delta=\frac{\varepsilon n^r}{N}$ and $\mu=\frac{kN}{n^{r-1}}$ where $N=|A_1|\ …
- 3,446
1
vote
Digraphs with exactly one Eulerian tour
Here is a combinatorial proof I found.
First, note that this is equivalent to allowing loops but demanding that all vertices have indegree and outdegree 2 (add a loop to each vertex of in/outdegree 1) …
- 3,446