All Questions
90 questions
1
vote
1
answer
99
views
Is there any known upper bound for the local crossing number of a graph drawing in the plane?
The local crossing number ${\rm LCR(G)}$ of a graph $G$ is defined as the least nonnegative integer $k$ such that the graph has a $k$-planar drawing. In other words, it is the smallest possible number ...
- 21
1
vote
0
answers
51
views
Coarse-graining a hypergraph
$\DeclareMathOperator{\poly}{\mathrm{poly}}$I have asked this question on math.SE here, but couldn't get a satisfactory answer. I have also asked a related question on math overflow here, but haven't ...
- 277
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)$ ...
- 63.9k
0
votes
1
answer
98
views
Chromatic tiling complexity and the chromatic number conjecture
Let $T$ be a finite set of tiles in $\mathbb{R}^d$. A tiling of $\mathbb{R}^d$ by $T$ is a collection of disjoint translates of tiles in $T$ whose union is $\mathbb{R}^d$. A tiling is $k$-chromatic if ...
- 18.7k
1
vote
1
answer
115
views
Bounds on lengths of boxes in bounded-degree box graphs
$\DeclareMathOperator{\box}{\operatorname{box}}$$\DeclareMathOperator{\cub}{\operatorname{cub}}$
This is a follow up and an extension of another question I asked recently.
A box graph is a graph ...
- 277
1
vote
1
answer
194
views
Bounds on lengths of intervals in bounded-degree interval graphs
A graph is said to be an interval graph if its vertices can be associated with (closed) intervals on the real line $\mathbb R$ and there is an edge between two vertices if and only if the ...
- 277
1
vote
1
answer
141
views
Covering a bounded degree graph with subgraphs of bounded sizes
Let $G$ be a connected graph on $n$ vertices with maximum degree $\Delta \ge 2$. Let $\mathcal G = \{G_1,G_2,\ldots\}$ be a collection of subgraphs of $G$ such that every edge of $G$ is contained in ...
- 242
1
vote
0
answers
67
views
Conjecture on the increasing efficiency of the shortest minimum-link polygonal chains covering any grids of the form $\{0,1,2\}^k$ as $k$ grows
From the well-known Nine dots problem, we know that we need a polygonal chain with at least $4$ edges to connect the $9$ points of the planar grid $G_{3,2}:=\{\{0, 1, 2\} \times \{0, 1, 2\}\} \subset \...
- 1,451
1
vote
0
answers
42
views
What lower bounds are known for pair crossing number and related questions in multigraphs?
So in terms of crossing number https://arxiv.org/pdf/1808.10480 gives a lower bound of $O(e^{2.5}/n^{1.5})$ for multigraphs with no face of length 2 with no node contained inside.
What do we know ...
- 111
1
vote
1
answer
114
views
Removing a face from 4-connected planar graph
After removing a face (vertices along with edges) of a 4-connected planar graph, is the remaining graph 4-connected? Alternatively under what conditions is this true?
- 4,219
2
votes
1
answer
209
views
Do the dual graphs of hyperplane arrangements admit Hamiltonian paths?
Consider a simple hyperplane arrangement $H_1,\cdots,H_n$ in the Euclidean space $\mathbb{R}^d$. By "simple" we mean any $k$ hyperplanes in $\{H_1,\cdots,H_n\}$ intersect in codimension $k$. ...
- 6,101
2
votes
1
answer
106
views
Exhaustive list of small graphs for which $\frac{\alpha(G)\omega(G)}{n}$ is small?
I am looking for a list of small graphs (say on less than 10 vertices) for which the parameter $p(G) = \frac{\alpha(G) \omega(G)}{n}$ is small. Here $\alpha(G)$ and $\omega(G)$ is the size of the ...
- 3,499
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 (...
- 32.1k
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 ...
- 32.1k
2
votes
0
answers
87
views
Computationally decomposing a complete geometric graph into forests of stars
I'm working on the following problem:
I would like to see if it possible to decompose a complete geometric graph on $8$ vertices into $5$ planar star-forests. As doing this by hand was hopeless, I ...
- 63.9k
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)$ ...
- 1,075
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
2
votes
0
answers
126
views
Checking existence of a non-crossing Hamiltonian path in geometric graphs
I am interested in the following computational problem. Given a geometric graph (i.e, a graph drawn in the plane so that its vertices are represented by points in general position and its edges are ...
- 4,219
2
votes
0
answers
65
views
Structure Theory for Tree Decompositions
I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer.
Is is known when $G$ admits the following type of ...
- 21
2
votes
1
answer
157
views
Bound for a sequence of vertices in a graph
I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be any $k$-regular connected directed graph with $n$ vertices, no parallel edges and no 2-cycles. For a vertex $v\in G$, let $...
- 167
1
vote
0
answers
54
views
Chromatic number of 2-graph vs hypergraph of point-line incidences
Define the chromatic number $\chi(H)$ of a (hyper)graph $H$ as the smallest $k$ such that its vertices can be $k$-colored such that no (hyper)edge is monochromatic.
Given a finite set of points $P$ in ...
- 18.7k
0
votes
0
answers
183
views
Covering discrete triangle with generalized knight jumps
Consider for $n\in\mathbb{N}, n\geq 6$ the discrete triangle $\nabla=\{(i,j)\in \{1,\ldots,n-1\}^2 \mid j\leq n-i\}$. This is basically the lower "half" of a chess board if you cut it along ...
- 91
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 ...
- 63.9k
2
votes
0
answers
51
views
Regular graphs of tangent spheres
Problem 1. Let several non-overlapping spheres in $\mathbb{R^3}$ are given. For which $n$ it is possible that each sphere is tangent to exactly $n$ other spheres?
Consider the smallest sphere. Since ...
- 691
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
2
votes
1
answer
312
views
Pairwise intersecting circles in the plane
If I am looking at a collection $\mathcal{C}$ of circles $\{C_1,...,C_n\}$ all of which have some radii $\{r_1,...,r_n\}$ where $r_i\in\mathbb{R}^{+}$ for each $i \in[n]$. In $\mathcal{C}$, all the ...
- 539
1
vote
1
answer
66
views
Representation of $x$-non-monotone curves with one intersection each by $x$-monotone curves
Take the $y$-axis and a set of $n$ curves starting from $y$-axis, labelled as $\mathcal{C}:=\{C_1,C_2,...,C_n\}$. These curves fulfill the following conditions:
The curves all have a starting point ...
- 18.7k
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 ...
- 857
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 ...
- 1,851
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 ...
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 ...
- 32.1k
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 ...
- 32.1k
0
votes
0
answers
52
views
What do optimal tours tell about finite point sets?
Let $T_{\mathrm{MIN}}$ and $T_{\mathrm{MAX}}$ denote the shortest, resp. longest Hamilton cycle through a set of $n=2k+1$ points.
Let further $S_{\mathrm{MIN}}$ and $S_{\mathrm{MAX}}$ be the "...
- 13.2k
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 ...
- 5,822
2
votes
1
answer
127
views
The density of a tripartite 1-planar graph
1-planar graphs are those can be drawn in the plane so that there is at most one crossing per edge. We know that the maximum number of edges of an $n$-vertex 1-planar graph is at most $4n-8$, and the ...
- 1,190
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
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
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 ...
- 32.1k
3
votes
0
answers
134
views
Two questions on counterexamples to Borsuk's conjecture and ball-packings
In 1933 Karol Borsuk conjectured the following
Can every bounded subset $E$ of $\mathbb{R}^d$ be partitioned into $(d+1)$ sets, each of which has a smaller diameter than $E$?
Whilst new to this ...
- 63.9k
3
votes
0
answers
83
views
Distance spectra of uniform tilings
Let a uniform tiling be defined by a vertex configuration $(n_1.n_2.\cdots.n_k)^m$, which is either spherical, Euclidean or hyperbolic. Assume that the tiling is vertex-transitive, especially that ...
- 9,720
0
votes
1
answer
249
views
Oriented path in a graph
Let $G=(\mathcal{V}_G,\mathcal{A}_G)$ be an oriented acyclic graph. Assume that $G$ has a unique source $s\in \mathcal{V}_G$ and a unique sink $t\in \mathcal{V}_G$. Now, fix $u,v\in \mathcal{V}_G$ ...
- 3,446
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
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 $...
- 7,875
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 ...
- 290
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 ...
- 46
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
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 ...
- 984
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
1
vote
1
answer
75
views
Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph, what is the smallest number of "curves"?
Given a vertex $u$ (of bounded degree $k$) and another vertex $v$ in a planar graph $G$, what is the smallest number of "curves" in the plane drawn from $u$ to $v$ such that no $u$--$v$ path in $G$ ...
- 32.1k