All Questions
Tagged with ag.algebraic-geometry graph-theory
37 questions
74
votes
29
answers
8k
views
Proofs where higher dimension or cardinality actually enabled much simpler proof?
I am very interested in proofs that become shorter and simpler by going to higher dimension in $\mathbb R^n$, or higher cardinality. By "higher" I mean that the proof is using higher dimension or ...
51
votes
3
answers
4k
views
What is the sandpile torsor?
Let G be a finite undirected connected graph. A divisor on G is an element of the free abelian group Div(G) on the vertices of G (or an integer-valued function on the vertices.) Summing over all ...
- 19.2k
18
votes
2
answers
700
views
Can all unit-distance graphs have their vertices at algebraic integers?
A graph $G$ is described as a unit-distance graph if there exists a function $f:G \rightarrow \mathbb{C}$ such that for every edge $(u,v) \in E(G)$, we have $|f(u) - f(v)| = 1$.
Obviously, we can ...
- 12.4k
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
3
answers
1k
views
A question on representation of graphs
Take a complete graph $K_n$. You want to assign a vectors from $\Bbb F_2^d$ to every edge such that sum of vectors in every simple cycle does not sum to $0$ vector. The question is what is minimum $d$ ...
- 13.9k
12
votes
0
answers
325
views
Is there an algorithm to compute a Belyi map for the Riemann surface?
Let $y^2=x^5-x-1$ be an affine model of a projective complex curve, is there an algorithm to compute the Belyi map (preferably of small degree), i.e., map to the projective line ramified only at $\{0,...
- 269
11
votes
1
answer
267
views
What is the chromatic number of the "conic hypergraph" on a non-singular plane cubic?
Can we color the points of a complex non-singular plane cubic curve with finitely many colors so that no conic intersects the curve at 6 distinct points of the same color?
If so, what is the smallest ...
- 85.6k
10
votes
3
answers
671
views
Is there a continuous analogue of Ramanujan graphs?
I think it might help to think of the following definition of a Ramanujan graph - a graph whose non-trivial eigenvalues are such that their magnitude is bounded above by the spectral radius of its ...
- 617
8
votes
1
answer
1k
views
Beyond an intro to topological graph theory...
I'm looking to find out what active areas of research there are in topological graph theory, particularly those that interface strongly with other areas of math (say, group theory, algebraic topology, ...
- 1,180
8
votes
2
answers
920
views
Is there an algorithm to compute efficiently the dessin d'enfant from a Belyi pair?
Let $(X,f)$ be a Belyi pair, i.e. a Riemann surface $X$ together with a morphism $f: X \to \mathbb{P}^1$, ramified only in $0,1, \infty$. Grothendieck's dessin d'enfant is the pre-image $G$ of the ...
- 4,070
8
votes
2
answers
692
views
Enumeration of graphs arising in invariant theory
I've been working on a talk based on some stuff in Olver's "Classical Invariant Theory" book and have been wondering about a related graph enumeration problem.
Start with a triple $(n,v,e)$ of ...
- 16k
8
votes
1
answer
421
views
p-adic versions of log concavity for graphs (or matroids)
It was recently shown using techniques inspired by algebraic geometry (by Huh and Adiprasito-Huh-Katz) that the chromatic polynomial of a graph (or matroid) has coefficients that satisfy log-concavity....
- 7,746
6
votes
1
answer
426
views
Graphs of lines on del Pezzo surfaces
Let $k$ be an algebraically closed field. To any del Pezzo surface $S$ over $k$ we may associate its graph of lines, which has one vertex for each line and an edge (with multiplicity if required) ...
- 21.3k
6
votes
1
answer
722
views
Ihara zeta function
Is there a natural connection between the Ihara zeta function of a graph,
and (for instance) the Riemann zeta function of certain varieties over finite fields ?
Thanks.
- 4,547
5
votes
1
answer
368
views
Six people standing on earth
Consider 6 people $p_i$, $i=1,\dots 6$, standing on a sphere $S^2$. We label the positions of these people by $p_i$ again. Suppose no pair of these points $p_i$ are antipodal. At each point $p_i$ ...
- 434
5
votes
0
answers
121
views
The Smith decomposition of the graph Laplacian and Locality
Let $X$ be a graph. Let $V(X)$ and $E(X)$ be the sets of vertices and edges of the graph respectively. If $f:V(X) \rightarrow G$ where $G$ is an abelian group, then one can define a graph Laplacian as ...
- 51
5
votes
0
answers
230
views
Minimal algebraic degree of symmetric unit distance embedding of Heawood graph
I'm looking at embeddings of the Heawood graph in the plane as unit distance graph. Apparently the first such embedding was given by Gerbracht, 2009 and has algebraic (over the rationals) coordinates ...
- 10.7k
4
votes
0
answers
127
views
Measuring the failure of basepoint independence of the rotor-routing model for non-planar ribbon graphs
In this question from 2012, Jordan Ellenberg asks if the set of spanning trees of a graph $G$ is naturally a torsor for the critical group (also called the sandpile group or the picard group $Pic^0(G)$...
4
votes
0
answers
972
views
Questions about dessin d'enfants, trees and their Shabat polynomials
This will be a series of questions, a few of which have been troubling me for quite a while now. Before I jump right in, let me first introduce a few notions which I will assume.
(Note: All of these ...
- 829
3
votes
1
answer
177
views
Intersection graph of $(-1)$-class divisors on surface of general type
Let $X$ be a rational surface, say $X$ is del Pezzo surface. Let $D$ be $(-1)$-class divisor, i.e: $D^2=-1$ and $D^2+D.K_X=-2$. It is easy to show that on del Pezzo surface any $(-1)$-class divisor is ...
- 1,982
3
votes
3
answers
330
views
Voronoi and Delaunay
Please provide some references on Voronoi and Delaunay decompositions which is mathematically written. I mean I can find several texts or links on this written for computer science students without ...
user111251
3
votes
1
answer
132
views
Is a simply connected locally 2-connected complex a union of spheres and planes?
Let $X$ be a (potentially infinite) 2-dimensional simplicial complex. Then each link at a vertex $x\in X$ is a graph.
Question. If $X$ is simply connected and each link is 2-connected (in the sense ...
- 13.6k
3
votes
1
answer
1k
views
Dual (/reduction?) graph of a curve
This might be a bit of a broad question, or maybe even questions.
Recently I have learned about the connection between algebraic geometry and graph theory, via the dual graph of a curve. I have also ...
- 5,504
3
votes
2
answers
632
views
Configuration of the branch locus of a branched covering of an elliptic curve
Let $C$ be a curve of genus 3 and suppose that it admits a branched cover $\varphi:C\rightarrow E$ with $E$ elliptic and such that $\varphi$ does not factor through any \' etale cover. Then the degree ...
- 33
3
votes
2
answers
246
views
Topological Complexity $TC$ of two robots moving on number $8$
I have been working on my research as a student at Wilbur Wright College on Topological Complexity. We solved the problem of two robots moving on a circle and letter $T$ using Farber's theorem but ...
- 33
3
votes
1
answer
215
views
number of ribbon structures (or punctured surfaces) on a graph
Suppose $G$ is connected undirected graph.
Does the calculation of the number of topologically distinct punctured surfaces that can arise from putting a ribbon structure on $G$ exist in the ...
- 47
3
votes
0
answers
157
views
F-vectors of simplicial complex and f-vectors of non-faces of simplicial complex
Is there any result which gives us a relation between f-vector of simplicial complex and f-vector of nonfaces of a simplicial complex?
Thank you
- 51
3
votes
0
answers
190
views
Construction of algebraic curves using line bundles on graphs
In this paper http://arxiv.org/abs/0707.1309 Matthew Baker and Serguei Norine, construct a analogue of the Riemman Roch formula for Lineal Systems defined on graphs. In the paper http://arxiv.org/abs/...
- 527
3
votes
0
answers
98
views
Reconstructing a function from its variants that negate one argument
Call two functions $g(x_1,\ldots,x_n)$ and $h(x_1,\ldots,x_n)$ from complex numbers to complex numbers equivalent if they are the same up to the order of their arguments. Formally: there is a ...
- 37.7k
2
votes
1
answer
285
views
Minimum length path touching $n$ circles
Given $n$ non-overlapping circles of radius $1$ (i.e., the distance between the centers of any two circles is greater than $2$), how to find the minimum length path (the path can be of any form) that ...
- 367
2
votes
1
answer
196
views
Circuit Reduction on Dual Graph of an Algebraic curve
I want to compute the resistance function r(p,q) between any two vertices of a fairly complicated graph. This resistance function is the one in Admissible pairing on a curve by Shouwu Zhang, section 3 ...
- 727
2
votes
0
answers
143
views
Optimization over Spectral Laplacian in cycles and trees
Is there any idea on how one can deal with an optimization problem of sum of k largest eigenvalues(min) of Laplacian matrix of a simple cycle or tree?
I would like to use semidefinite programming for ...
- 161
1
vote
1
answer
258
views
How to compute graph ideal or cut ideal of a graph?
Graph ideals are a special case of Stanley-Reisner ideal, explained in Combinatorial Commutative Algebra book by Sturmfels, and graph ideals here. Graph ideals are generated by the minimal paths while ...
- 143
1
vote
0
answers
100
views
Varieties determined by a characteristic-type of polynomial with the structure of an underlying graph
While writing my master thesis, following problem came up:
Given a digraph $G$ with edges $e_1,..,e_n$ and a
given a $n\times n$- matrix $A\in\mathbb{C}^{n\times n}$ such that $A_{ij}=0$ if the ending ...
- 33
0
votes
3
answers
622
views
When does the rigidity matrix of a graph have full row rank?
Intuitive description: In the 2D plane, there are $m$ bars connected by $n$ joints. The length of each bar is fixed. These joints and bars can be viewed as a graph (see the figures below). Denote $s_i$...
- 61
0
votes
0
answers
64
views
Relation between a cycle on a toroidal graph and divisors of elliptic curve over complex plane
I am very new to algebraic geometry. I was reading about divisors on a scheme. I am wondering does there is some connection between the followings.
An elliptic curve over the complex plane we can ...
- 613
0
votes
0
answers
57
views
Reference for packing property and König property
Can someone please suggest reference material to study about the packing property and König property of ideals and some examples?
- 21