All Questions
90 questions
36
votes
0
answers
2k
views
3-colorings of the unit distance graph of $\Bbb R^3$
Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$.
Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = (\alpha,...
- 17k
24
votes
3
answers
2k
views
Gauss-Bonnet Theorem for Graphs?
One can define the Euler characteristic χ for a graph as the number of vertices minus the number of edges. Thus an $n$-cycle has $\chi = 0$ and $K_4$ has $\chi=-2$.
Is there an analog for the ...
- 151k
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
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
1
answer
1k
views
Monomer-Dimer tatami tilings need better relationships with other math. Summary of results
A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the tatami condition if no four tiles meet at any point. (Or you can think of it as the removal of a matching from ...
19
votes
2
answers
1k
views
Is it possible that both a graph and its complement have small connectivity?
Let $G=(V,E)$ be a simple graph with $n$ vertices. The isoperimetric constant of $G$ is defined as
$$
i(G) := \min_{A \subset V,|A| \leq \frac n2} \frac{|\partial A|}{|A|}
$$
where $\partial A$ is ...
- 1,991
18
votes
1
answer
1k
views
Sperner's Lemma implies Tucker's Lemma - simple combinatorial proof
Sperner’s Lemma is often called the "combinatorial analog" of Brouwer’s Fixed Point Theorem, and similarly Tucker’s Lemma is often called the combinatorial analog of Borsuk–Ulam’s Theorem.
We can ...
- 6,917
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
16
votes
4
answers
1k
views
Squaring a square and discrete Ricci flow
Is this a theorem?
Every $3$-connected planar graph $G$ may be represented as
a tiling of a square by squares,
one square per node of $G$, with nodes connected in $G$
corresponding to tangent squares....
- 151k
16
votes
1
answer
546
views
Chromatic numbers of infinite abelian Cayley graphs
The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...
- 19.2k
13
votes
2
answers
2k
views
Counting Hamiltonian cycles in $n \times n$ square grid
I wonder if anyone has counted these curves, either exactly or asymptotically?
Let $S_n$ be an $n \times n$ subset of $\mathbb{Z}^2$ consisting of $n^2$
lattice points: a lattice square.
Define a ...
- 151k
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
11
votes
5
answers
506
views
What are efficient pooling designs for RT-PCR tests?
I realize this is long, but hopefully I think it may be worth the reading for people interested in combinatorics and it might prove important to Covid-19 testing. Slightly reduced in edit.
The ...
- 14.4k
11
votes
1
answer
348
views
Chromatic number of a graph defined by $n$ lines on the plane
Given $n$ lines on the plane, consider all their intersection points. Find the minimal number $d=d(n)$ such that they may be always colored in $d$ colors so that on each line any two consecutive ...
- 109k
11
votes
1
answer
370
views
Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?
Is the following lemma a well known result in graph theory?
I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...
- 6,917
10
votes
1
answer
1k
views
How can we find n points on a plane so that as many pairs of points as possible have the same distance?
There are $n$ points on the plane, and we need to maximize the number of pairs of points which have the same Euclidean distance.
- 159
10
votes
3
answers
1k
views
"incidental" intersections of a complete graph in the plane
Given a complete graph of n vertices (no three of which are no collinear) in the plane and straight edges, what is the maximal possible number of "incidental intersections" of edges, i.e., number of ...
- 386
10
votes
1
answer
370
views
When does a graph have a circular orientation? Or equivalently can anyone help me characterize this particular class of $3$-colorable perfect graphs?
Call an oriented digraph $D=(V,A)$ circular when for all $\small x,y,z\in V$ if $(x,y)\in A$ and $(y,z)\in A$ then $(z,x)\in A$ or equivalently if $D$ is any oriented digraph whose arc set is a ...
- 2,506
9
votes
3
answers
436
views
Labeling edges of an icosahedron with sum constraints
The question is inspired by this previous MO question. There it was shown that it's possible to label the edges of a cube by the numbers $\{1,2,\ldots,6,8,9, \ldots, 13\}$ in such a way that:
Three ...
- 20.8k
9
votes
3
answers
2k
views
Embedding planar graphs into the grid
I've seen the following lemma in a paper. The result is by Valiant.
A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...
- 903
9
votes
3
answers
470
views
Is it possible that every edge in a 1-planar drawing with minimum number of crossings is crossed?
A graph is 1-planar is it has drawing in the plane so that each edge is crossed at most once. Here we also assume the drawing satisfies (1) no edge is self-crossed; (2) no two adjacent edges are ...
- 557
9
votes
2
answers
484
views
Connected geometric thickness two
A graph $G = (V,E)$ has geometric thickness two if there exists an embedding $\varphi: V \rightarrow \mathbb{R}^2$ and a decomposition $E = E_1\cup E_2$ such that $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ ...
- 479
8
votes
2
answers
615
views
Embedding of planar graphs
I've recently come across the following lemma.
Lemma (Valiant): A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...
- 83
8
votes
2
answers
340
views
Graphs with prescribed numbers of k-cliques
Let $(a_1,a_2,\dots, a_n)$ be a sequence of non-negative integers.
Q. When does there exists a simple graph $G$ such that its number of $k$-cliques is $a_k$ (that is $G$ has $a_1$ vertices, $a_2$ ...
- 1,540
7
votes
4
answers
4k
views
Number of spanning trees in a grid
Given a $\sqrt{n}\times\sqrt{n}$ piece of the integer $\mathbb{Z}^2$ grid, define a graph by joining any two of these points at unit distance apart. How many spanning trees does this graph have (...
- 3,511
7
votes
2
answers
962
views
Maximal number of edges and triangular cells for n points in a triangular lattice
Consider a subset of $n$ points in an equilateral triangular lattice. Draw all the edges between nearest-neighbor points.
What is the maximum, over all such subsets, of the number of edges? This ...
- 567
7
votes
1
answer
760
views
Difference Sets
Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
- 123
7
votes
1
answer
153
views
Above/below directed graph on cells of arrangement of lines
This question concerns the structure of a directed graph
built on the cells of an arrangement of lines.
My basic question is whether this graph has been
studied before, perhaps in another guise. I ...
- 151k
6
votes
1
answer
122
views
Have this generalization of Indifference graphs been studied before?
Indifference graphs are those graphs $G=(V,E)$ for which there exists a real-valued function $f$ defined on $V(G)$ such that, if $u$ and $v$ are distinct vertices, $|f(u)−f(v)| \lt 1$ if and only if $\...
- 519
6
votes
2
answers
268
views
Counting valid coordinates
We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in \...
- 323
6
votes
1
answer
142
views
Embedding linklessly embeddable graphs without Borromean rings
A linklessly embeddable graph is a graph which can be embedded into $\Bbb R^3$ so that no two of its cycles are linked. For example, the Petersen graph is not such a graph.
Now, I can think of another ...
- 13.6k
6
votes
0
answers
657
views
Unique domino tiling
Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property?
Definitions:
A subset $S$ of the $xy$-plane is star-convex if there ...
- 1,090
5
votes
1
answer
213
views
Given a 3-connected graph $G$, is there an edge $e$ so that both $G-e$ and $G/e$ are still 3-connected?
Let $G$ be a 3-connected (simple) graph other than $K_4$. In Diestel's "Graph Theory" Section 3.2 we find
Lemma 3.2.2. There is an edge $e$ so that $G\mathbin{\dot-}e$ is still 3-connected (...
- 13.6k
5
votes
3
answers
363
views
Perimeter/Neighborhood of a graph on grid
Hello,
I have a $\sqrt{n}\times\sqrt{n}$ lattice graph $G=(V,E)$ i.e. vertices on said 2-dim integer lattice, and two vertices have an edge if their $L_1$ distance is one.
Now I want to claim ...
- 93
5
votes
3
answers
748
views
Aperiodic graphs
The concepts of being non-periodic and aperiodic for tilings have obvious versions for connected graphs with a countable set of vertices and a finite number of edges meeting at each vertex. A graph $G$...
- 329
5
votes
0
answers
76
views
Is the choosability/list chromatic number of a circular arc graph equal to its chromatic number?
In 2003, Prowse and Woodall proved that for graphs $C_n^k$ which are powers of cycles,
$$\chi_\ell(C_n^k) = \chi(C_n^k).$$
They conjectured that this equality holds for the broader class of graphs ...
- 151
4
votes
2
answers
512
views
Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?
Given $n$ and $t$ lengths $ l_i, 1\leq l_1<l_2<\cdots<l_t\leq n-1$, of directed diagonals within an $n$-gon such that $l_1+\cdots+l_t\neq 0 \pmod n)$. Does it exist a directed path within ...
- 221
4
votes
1
answer
444
views
What is the significance of ear decompositions for non-graphic matroids?
On Wikipedia there is subsection in the article on ear decompositions of graphs titled "Matroids":
Now as defined above, the circuits of a matroid can not always be listed to satisfy the ...
- 2,506
4
votes
1
answer
421
views
Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles intersect?
Can $n$ circles on a plane generate $m$ intersection points where at least $k$ circles intersect?
For $k = 2$ the answer is obvious since we can always place circles so that every one of them ...
- 63
4
votes
1
answer
187
views
Number of permutations with combinatorial geometric constraints
We are given a $d$-dimensional hypercube $H$, where each vertex is labeled with an integer $\ell\in\{1, 2, \ldots, 2^d\}$. Let $L$ be this labelling.
Question: How many labelling permutations $L'$ of ...
- 1,677
4
votes
1
answer
235
views
Graphs with adjacency matrix depending on associated-vector distances
Let $G$ be a graph of order $n$ such that for each vertex $v$ there are two associated vectors, $f_v, g_v\in R^n$, where $uv\in E(G)$ if and only if $\|f_u - f_v\|^2 \ge \|g_u-g_v\|^2$.
ISGCI didn't ...
- 519
4
votes
0
answers
90
views
Definition of Loop in an Oriented Matroid
I had posted this on Stackexchange because I don't believe this is a particlarly difficult question, but there were no answers, so I'm posting it on here now.
I just had a quick question about the ...
- 61
4
votes
0
answers
66
views
Convergence of graph geodesics to geodesics on metric spaces
Let $(X,d)$ be a compact length space metric space $\mathbb{X}_{\delta}$ be a $\delta$-packing on $X$ and, for every $k\in \mathbb{N}_+$, let $G_{k,\delta}=(\mathbb{X}_{\delta},\mathcal{E}_k,W_k)$ ...
- 364
4
votes
0
answers
94
views
Finding closest set of K disjoint hyperspheres to a point in $\mathbb{R}^n$ with uniform radius
I am interested in the following problem: in $\mathbb{R}^n$, we have $N$ overlapping hyperspheres all with the same radius. Given a point $p$ in $\mathbb{R}^n$, the objective is to find the $K$ non ...
- 161
3
votes
4
answers
379
views
Generalization of independence complex of graphs
Let $G$ be an undirected graph with no multiple edges or loops. Recall that the independece system $\mathcal{I}(G)$ consists of all those subsets $A$ of the vertex set such that the induced subgraph $...
- 1,017
3
votes
2
answers
455
views
How to generating all flats of the cycle matroid of a graph?
If $M$ is a matroid, I can use M.flats(k) in SageMath to list all the flats of rank $k$. But I hope that there is an algorithm or program to list all flats of the cycle matroid of a graph. And do not ...
- 51
3
votes
1
answer
201
views
How many non-homeomorphic surfaces arise from these graphs?
Take an undirected graph $G$, where every vertex has at least two edges (we count self-loops as two edges). For each vertex $v$, we define a regular deg($v$)-gon. For each edge between $v_1$ and $v_2$,...
- 6,353
3
votes
1
answer
344
views
Enumerating Connected Circle Graphs
Hi
A circle graph is defined as the intersection graph of a set of chords of a circle.
I'm interested in any information which might help to enumerate connected circle graphs.
Thanks
Andy
- 239
3
votes
1
answer
157
views
Structure of boundary labelling in Sperner‘s Lemma
Consider a triangulated polygon in the 2-dimensional plane, where each vertex is labelled green, blue, or orange. Sperner's Lemma asserts that a fully-colored triangle exists in the triangulation, if ...
- 6,917
3
votes
0
answers
144
views
Counting homologically non-trivial and trivial cycles in $n \times n$ square lattice torus of a given length $l \geq n$
This should be a fairly standard question but I can't really seem to find a reference.
Consider an $n \times n$ square lattice torus $\mathbb T$. Given a length $l \geq n$, what is the number of ...
- 269