All Questions
184 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
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
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
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
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
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
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
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
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
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
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
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
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
0
answers
228
views
Is there a term for this graph subset?
Suppose $G$ is a (finite) graph which is $k$-vertex colourable (i.e. $\chi(G)\leqslant k$). Suppose $S$ is a set of vertices of $G$ with the following property:
If $c:V(G)\rightarrow [k]$ is a vertex ...
- 211
10
votes
3
answers
932
views
"Gluing and copy" graphs
Consider the minimal class of (simple, undirected) connected graphs (strictly speaking, isomorphism classes of connected graphs) which contains a single vertex $K_1$, and is closed under following ...
- 109k
10
votes
2
answers
1k
views
History of deletion-contraction formula
The following is known as deletion-contraction formula:
Assume $\Gamma$ is a connectted graph with edge $\rho$ then
$$t(\Gamma)=t(\Gamma\backslash\rho)+t(\Gamma/\rho),$$
where $\Gamma\backslash\...
- 45k
10
votes
2
answers
728
views
Bounds on chromatic number of $k$-planar graphs
A $1$-planar graph can be drawn in the
plane so that each arc is crossed at most once by another arc.
A $k$-planar graph can be drawn so that each arc is crossed at most $k$ times.
Planar graphs are ...
- 151k
10
votes
2
answers
962
views
Surveys of the items of Erdős' "toolbox"
Could you point out some survey papers and monographs that highlight the kernel of tricks, techniques, and tools that Paul Erdős employed the most in his research work (in particular in graph theory, ...
10
votes
3
answers
490
views
How many colors do we need to avoid bichromatic triangles?
Ramsey theory studies whether a monochromatic subgraph (more generally, structure) appears when we color the edges of a complete graph with some colors.
I wonder if the following type of question has ...
- 19k
10
votes
1
answer
269
views
Edge-transitive Cayley graphs of $S_n$
I came across the following question which I haven't seen before:
Question. Fix $k\ge 3$. For infinitely many $n$, does there exists a generating set $\langle R_n \rangle = S_n$, $|R_n|=k$, such ...
- 17k
10
votes
1
answer
223
views
Kneser subgraph with high chromatic number
For positive integers $n\geq 2k$, it is known that the chromatic number of the Kneser graph $K_{n,k}$ is $n-2k+2$. Moreover, the Schrijver graph $S_{n,k}$ (definition in the same link), which is a ...
- 223
10
votes
1
answer
492
views
is there a ‘nice’ lattice on the set of unlabelled graphs with $n$ vertices?
It is easy to endow the set of vertex-labelled graphs with $n$ vertices with a lattice structure: take the union and the intersection of the edge set as meet and join respectively.
However, I wonder ...
- 5,822
10
votes
1
answer
526
views
Maximum number of triangles no two of which have a common edge
For $n\in N_+$, define $f(n)$ to be the maximum number of triangles in a graph $G$ with $n$ vertices, taken over all $n$-vertex graphs having the property where no two triangles have a common edge.
Do ...
- 475
9
votes
2
answers
2k
views
"Gray code" of all permutations
Informally asking, can we step through all permutations of the set $\{1,\ldots,n\}$ by just using transpositions?
More formally: For any $n\in\mathbb{N}$ let $[n] = \{1,\ldots,n\}$ and let $S_n$ be ...
- 48.9k
9
votes
1
answer
261
views
Expansion in strongly regular graphs
Have you seen the following statement proven anywhere?
Let $G$ be a strongly regular graph with parameters $(n,k,\lambda,\mu)$ with $\lambda,\mu>0$. Then there is no set $A$ of at least $n/4$ ...
- 93
9
votes
1
answer
399
views
Are bipartite Moore graphs Hamiltonian?
This is motivated by a computer-generated conjecture that bipartite distance-regular graphs are hamiltonian. I decided to check the case of Moore graphs first.
The cycles and complete bipartite graphs ...
- 9,501
8
votes
4
answers
1k
views
Counting with trees
Let $\mathcal{U}_n$ denote the set of unrooted unlabelled trees with $n$ edges. For $T\in\mathcal{U}_n$, let $1^{u_1}2^{u_2}\cdots n^{u_n}$ be its degree distribution, that is, $u_i=\#$ of vertices ...
- 43.2k
8
votes
3
answers
779
views
Computer program for counting graph homomorphisms
I would like to ask is there a computer program for counting graph homomorphisms?
- 4,826
8
votes
2
answers
813
views
A hypercube-related graph
For integer $n\ge 3$, consider the graph on the set of all even vertices of the $n$-dimensional hypercube $\{0,1\}^n$ in which two vertices are adjacent whenever they differ in exactly two coordinates....
- 23k
8
votes
2
answers
669
views
Fractional chromatic number, find reference to a particular alternate definition for
I'm searching for a reference to a particular alternate definition of the fractional chromatic number of graphs.
Let me review the most common definition and basic properties first.
Let $ G $ be ...
- 1,944
8
votes
1
answer
682
views
Red-blue alternating Menger's theorem
Suppose we have a graph where every edge is colored red or blue. We say that a path is alternating if the red and blue edges alternate in it. Our goal is to find many edge/vertex-disjoint alternating ...
- 19k
8
votes
1
answer
449
views
Does Vizing's conjecture hold for the infinite graphs?
In finite graph theory, there are many (in)equalities which relate the integer value of a certain graph invariant (e.g. domination or chromatic number) for the product of two finite graphs (e.g. ...
8
votes
1
answer
488
views
Stephan Brandt's habilitation thesis
I am searching for a copy of Stephan Brandt's habilitation thesis, Dense graphs with bounded clique number. Brandt's thesis is from Freie Universität Berlin in 2001.
I've done what I can to track ...
- 462
8
votes
0
answers
181
views
Self-avoiding walks on strips
A strip is a locally finite graph which admits a quasi-transitive (i.e. finitley many orbits on vertices) action of $\mathbb Z$. A self avoiding walk is a walk which visits no vertex more than once.
...
- 2,671
8
votes
0
answers
149
views
Edge-colorings of plane graphs: do you know references where the following questions are studied?
Let $G$ be a plane graph (or more generally, a graph embedded on a surface) with a proper edge-coloring of $G$ with $k$ colors $\{1,\ldots,k\}$. I am interested in studying the cyclic permutations of ...
- 537
8
votes
0
answers
2k
views
What is the best lower bound for the domination number in regular graphs of girth 5?
The following theorem is a classical result (see [Alon and Spencer, The probabilistic method, 2nd ed., Theorem 1.2.2]):
Theorem: Let $G$ be a graph on $n$ vertices with minimum degree $d$. Then $G$ ...
- 161
8
votes
0
answers
152
views
Disjoint Rooted Paths with Specified Patterns
Let $S:=$ { $s_i : i \in [k]$ } and $T:=$ { $t_i : i \in [k]$ } be disjoint subsets of vertices of a graph $G$. Furthermore, let $A$ be a subset of $S_k$ (the symmetric group on $[k]$). A set of ...
- 32.1k
7
votes
2
answers
415
views
Graph which do not satisfy a pseudo-Poincaré inequality
Say that an infinite (connected) graph (with vertices of bounded degree) satisfies a $\ell_1$-pseudo-Poincaré inequality if there is a constant $C>0$ so that for any $n \in \mathbb{N}$ for any ...
- 4,432
7
votes
2
answers
595
views
A 2-page paper on a lower bound of Ramsey number
I'm looking for a 2-page paper on a lower bound of Ramsey number $R(a,b)$ for some constants $a$ and $b$. The paper was published in 80s or 90s. I googled it for a few days, but I cannot find the ...
- 71
7
votes
1
answer
142
views
equidistributed parameters on graphs
Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I wonder whether there are any 'interesting' combinatorial parameters $a,b: \mathcal G_n\to \mathbb ...
- 5,822
7
votes
2
answers
247
views
complicated combinatorial algorithms with good descriptions
For educational purposes, I am looking for an example of a complicated, elementary, but very well-explained combinatorial algorithm.
Such an example might be a bijection between two easily described ...