All Questions
Tagged with reference-request graph-theory
453 questions
69
votes
7
answers
17k
views
What is a chess piece mathematically?
Historically, the current "standard" set of chess pieces wasn't the only existing alternative or even the standard one. For instance, the famous Al-Suli's Diamond Problem (which remained ...
37
votes
2
answers
4k
views
How to find Erdős' treasure trove?
The renowned mathematician, Paul Erdős, has published more than 1500 papers in various branches of mathematics including discrete mathematics, graph theory, number theory, mathematical analysis, ...
34
votes
1
answer
789
views
Which graphs on $n$ vertices have the largest determinant?
This is a question that seems like it should have been studied before, but for some reason I cannot find much at all about it, and so I am asking for any pointers / references etc.
The determinant of ...
- 12.7k
32
votes
1
answer
2k
views
Should axiomatic set theory be translated into graph theory?
Recently I saw the abstract of a paper by Nash-Williams: ``Should axiomatic set theory be translated into graph theory?''. The abstract, taken from Mathscinet says the following:
The author ...
- 32.1k
30
votes
2
answers
3k
views
An unfair marriage lemma
I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem:
Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
- 32.4k
27
votes
1
answer
3k
views
Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946
I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph ...
- 419
26
votes
2
answers
4k
views
Why did Robertson and Seymour call their breakthrough result a "red herring"?
One of the major results in graph theory is the graph structure theorem from Robertson and Seymour
https://en.wikipedia.org/wiki/Graph_structure_theorem. It gives a deep and fundamental connection ...
- 290
25
votes
1
answer
3k
views
Number of hypercube unfoldings
While writing the code for this answer, I noticed that I not only could calculate the number of unfoldings of the $4$-cube, but also the number of the $n$-cube for more values of $n$. Basically, we ...
- 10.7k
24
votes
0
answers
760
views
How much of the plane is 4-colorable?
In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...
- 7,633
22
votes
5
answers
4k
views
Collection of conjectures and open problems in graph theory
Is there something similar to the Kourovka Notebook for graph theory (or anyway an organized, possibly commented, collection of conjectures and open problems)?
user60665
22
votes
2
answers
900
views
Is every 1-million-connected graph rigid in 3D?
It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$:
Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete ...
- 151k
21
votes
7
answers
1k
views
Reference for topological graph theory (research / problem-oriented)
I would be interested in recommendations for topological graph theory texts. I think Gross and Yellen has a great chapter on topological graph theory, and I find Mohar and Thomassen's Graphs on ...
20
votes
6
answers
4k
views
Graph theory from a category theory perspective
Are there any textbooks on graph theory written for a category theorist?
It would probably have to be on directed graph theory, but if there's some trick we can use to talk about undirected graphs as ...
19
votes
3
answers
2k
views
Are "almost all" strongly regular graphs rigid?
I have heard through the academic rumor mill (my advisor heard from so-and-so about a result they heard from big-name who saw it in some journal, etc.) of the following theorem:
Theorem: Almost all ...
- 432
19
votes
0
answers
782
views
Reference request: Parallel processor theorem of William Thurston
Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...
- 15.4k
18
votes
1
answer
6k
views
Intersection between category theory and graph theory
I'm a graduate student who has been spending a lot of time working with categories (model categories, derived categories, triangulated categories...) but I used to love graph theory and have always ...
- 30.3k
17
votes
3
answers
2k
views
Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$?
A graph $G$ is connected if and only if
the second-largest eigenvalue $\lambda_2$ of
the Laplacian of $G$ is greater than zero.
(See, e.g.,
the Wikipedia article on algebraic connectivity.)
Is ...
- 151k
17
votes
3
answers
2k
views
Applications of Kirchhoff's circuit laws to graph theory
Is there a good survey on applications of Kirchhoff's circuit laws to graph theory or/and discrete geometry?
Examples:
Matrix tree theorem,
Squaring the square,
Electrician’s proof of Euler’s ...
- 45k
17
votes
1
answer
1k
views
Which degree sequences are planar graphical?
The Erdős–Gallai theorem characterizes which degree sequences are graphical (i.e. realizable by a simple graph).
There has been some work on which degree sequences are planar graphical (i.e. ...
- 563
16
votes
5
answers
3k
views
Simple random walk on a locally finite graph: when is it recurrent?
I'm giving a talk tomorrow about a result in computer science which I recently proved. It's a recurrence-transience result on a random process which is related in spirit to a simple random walk. My ...
- 30.3k
15
votes
2
answers
755
views
Random noncrossing chords of a circle
Suppose you generate random chords of a circle, with endpoints selected uniformly over the circumference, rejecting any chord that crosses a previously generated chord.
The disk is then partitioned ...
- 151k
15
votes
1
answer
518
views
Reference request: Moore graphs
It is clear that the term Moore graph was coined by Hoffman and Singleton in their paper On Moore graphs with diameters $2$ and $3$, where they write
E. F. Moore has posed the problem of describing ...
- 2,339
15
votes
1
answer
746
views
Page-turning number of a graph
Motivation. As I was travelling in the UK, I used a physical copy of the "A-Z Road Atlas BRITAIN" for getting around. I was impressed that whenever I wanted to go from the map segment shown ...
- 48.9k
15
votes
2
answers
1k
views
When does graph minor containment imply subgraph containment?
Consider a path of length 3. Any graph G which contains this graph as a minor must also contain it as a subgraph. For paths of any length this is easy to prove.
In general this happens for any graph ...
- 1,332
15
votes
1
answer
1k
views
Has the technique of "sprinkling" been used in studying random matrices?
In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of ...
- 4,922
15
votes
0
answers
455
views
Grothendieck dessins d'enfants - current surveys or text you can recommend?
I was recommended this forum to be the leading site for algebraic geometry, so I would like to ask you a question about Grothendieck dessins d´enfants. My background is in maps on surfaces (graph ...
14
votes
4
answers
1k
views
Is the "Moebius Stairway" Graph Already Known?
It is a wellknown fact, that Moebius Ladder Graphs have $2n$ vertices, but nowhere could I find any hint of how to generalize them to Graphs with $2n+1$ vertices.
Last week I had the idea of giving up ...
- 13.2k
14
votes
1
answer
783
views
What was Smith's proof of Smith's theorem on Hamilton cycles in cubic graphs?
In a short 1946 paper "On Hamiltonian Circuits", Tutte proved the famous result that an edge in a cubic graph lies in an even number of Hamilton circuits.
He attributed the result to his friend CAB ...
- 12.7k
14
votes
0
answers
522
views
Reconstruction conjecture and partial 2-trees
Reconstruction conjecture says that graphs (with at least three vertices) are determined uniquely by their vertex deleted subgraphs. This conjecture is five decades old.
Searching relevant literature,...
- 281
13
votes
3
answers
3k
views
Koebe–Andreev–Thurston theorem - where can I find a proof?
Koebe–Andreev–Thurston theorem (known also as the circle packing theorem) says that any planar graph can be realized by a set of (interior-) disjoint disks corresponding to vertices, such that two ...
- 2,178
13
votes
2
answers
2k
views
What is the smallest 4-chromatic graph of girth 5?
It is known that the smallest 4-chromatic graph of girth 4 is the Grötzsch graph (11 vertices). What happens for girth 5?
The Brinkmann graph (21 vertices) has chromatic number 4, girth 5 and is 4-...
- 537
13
votes
1
answer
719
views
Homotopy theory for spanning trees of a graph
I am studying a paper of L. Lovász, ``A homology theory for spanning trees of a graph,'' but professor Babai has told me that Lovász later realized that this work is better framed in the language of ...
- 5,898
13
votes
1
answer
933
views
Drawings of complete graphs with $Z(n)$ crossings
Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly
$$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor \left\lfloor\frac{n-1}{...
- 6,101
13
votes
2
answers
748
views
Is there a version of Weyl's law for graph Laplacians?
Is there a version of Weyl's law or a local Weyl's law for eigenvectors of the graph Laplacian?
For some context, a colleague in statistics has encountered eigenvectors of the Laplacian for certain ...
- 6,001
13
votes
0
answers
237
views
A Dynkin type classification result in linear algebra
Let $G$ be a finite directed acyclic graph. The Cartan matrix $C_G=C$ of $G$ is defined as the matrix with rows and colums indexed by the vertices of $G$ and $c_{i,j}$ counts the number of paths from $...
- 26.5k
12
votes
5
answers
2k
views
Extensions of the Koebe–Andreev–Thurston theorem to sphere packing?
The Koebe–Andreev–Thurston theorem states that any planar graph can be represented
"in such a way that its vertices correspond to disjoint disks, which touch if and only if
the corresponding vertices ...
- 151k
12
votes
4
answers
1k
views
How dense is the set of asymmetric graphs?
On $n$ nodes, we have $2^{n(n-1)/2}$ graphs. Asymmetric graph is a graph that has only trivial automorphism. We known that asymptotically almost all finite graphs are asymmetric. Therefore, in the ...
- 2,993
12
votes
7
answers
769
views
Does the notion of graphs with vertex multiplicity exist?
I need to use graphs where each vertex gets a natural number, $b(v)$, its multiplicity. These numbers indicate how many 'replications' of the vertex we have.
It is actually a way to write in a ...
- 222
12
votes
1
answer
288
views
Cancelling a graph join from a graph homomorphism
Given (finite, simple) graphs $G$, $H$ and $K$ and a homomorphism
$$
G+K\to H+K
$$
where $+$ denotes the join, does it follow that there also exists a graph homomorphism $G\to H$?
If this is known, I'...
- 6,406
12
votes
3
answers
552
views
Estimate on currents in Cayley graphs
Take a Cayley graph $\Gamma$ (thought of as an electrical network with all edges having equal resistance) and break one edge $e$ and put a battery there. (Assume the graph has only one end* so that ...
- 4,432
12
votes
1
answer
424
views
Quantitatively characterizing the failure of the converse of Dirac's theorem
First, I am an undergraduate so I apologize if this is trivial and certainly understand if it is closed immediately.
I am currently in a combinatorics and graph theory class and recently we have ...
- 221
12
votes
1
answer
593
views
Characterizing graphs by their "walkers"
Let $G$ be a (large) graph and $W$ another (smaller) graph.
$W$ is what I call a walker.
Let me use "vertices" and "edges" for $G$ and
"nodes" and "arcs" for $W$.
$W$ has a distinguished node, its ...
- 151k
11
votes
2
answers
669
views
Which curves and surfaces are realizable by linkages? references?
Ok, so I try to formulate rigorously the question in the title, for which I am asking for references. My definitions may be flawed, so feel free to adjust/correct them! I care about dimensions 2 and 3 ...
- 2,041
11
votes
1
answer
269
views
Does every $C_4$-free bipartite graph lies in some finite projective plane?
A projective plane $Π$ is a 3-tuple $(P,L,I)$ where $P$ and $L$ are sets, and $I$ is a relation between $P$ and $L$, such that:
For every two elements $p_1$, $p_2\in P$, there exists a unique ...
- 9,501
11
votes
2
answers
391
views
When is the poset of acyclic orientations of a graph a lattice?
$\def\inv{\mathrm{inv}}\def\Acyc{\mathrm{Acyc}}$Let $G$ be a graph whose vertices are numbered $\{ 1,2, \ldots, n \}$. Given an orientation $\omega$ of $G$, define the inversions of $\omega$, written $...
- 156k
11
votes
1
answer
395
views
Dense triangle-free graphs and their independent sets
Recall that a graph is triangle-free if it does not contain a copy of $K_3$. Also, for a graph $G$, $\alpha(G)$ shall denote its independence number. Lastly, we will write $o(1)$ to denote quantities ...
- 3,499
11
votes
1
answer
337
views
Papers about decentralized search and cluster
I just start an independent study about small world network and clusters and I try to find papers about decentralized search and clusters.
Can anyone give me some references? Thanks!
EDIT (David ...
- 119
11
votes
1
answer
467
views
Correspondence between matrix multiplication and a graph operation of Lovász
In his book "Large networks and graph limits", Lovász describes a multiplication operation (he calls it concatenation) on "bi-labeled graphs". An $(m,n)$ bi-labeled graph is a ...
- 2,339
11
votes
1
answer
627
views
Representations of the automorphism group of graphs via spectral graphs theory
Given a (simple) graph $G=(V,E)$ with $V=\{1,...,n\}$ and let $A$ be its adjacency matrix.
I am interested in the representation theory (over $\Bbb R$) of the automorphism group $\def\Aut{\mathrm{Aut}...
- 13.6k
11
votes
0
answers
537
views
Outline of the unpublished proof of Erdős-Sós conjecture
In this post, it was mentioned that a long time ago, Ajtai, Kolmós, Simonovits, and Szemerédi announced a proof that for sufficiently large $k$, every $k$-vertex tree $T$ is a subgraph of every graph $...
- 3,499