New answers tagged

3 votes

Real-world examples of unweighted directed graphs

It's been recognized that adjacency matrix approaches to forming a spectral graph theory is problematic. It's been rediscovered that Eckmann's Combinatorial Hodge theory removes the problems and gives ...
Georg Essl's user avatar
4 votes

Real-world examples of unweighted directed graphs

Disclaimer: I am not an applied mathematician at all and I found this just via some basic Goolging. But the "Stanford Large Network Dataset Collection" (https://snap.stanford.edu/data/) ...
Sam Hopkins's user avatar
  • 22.8k
2 votes

When are (Abelian) Cayley graphs also expanders?

For what it's worth, a stronger statement is possible. Suppose $(G_n)$ is a sequence of finite groups. Moreover, suppose that there is an integer $k$ such that for all $n$, the derived length of $...
Mike Krebs's user avatar
1 vote

Deciding homomorphic images of De Bruijn graphs

This is quite relevant to my article Local Loop Lemma. I didn't know it is called De Bruijn graph back then, and I needed a slight modification for the paper but I essentially show that any digraph ...
Miroslav Olšák's user avatar
18 votes
Accepted

Can the Pythagorean Graph be finitely colored?

This paper shows that the chromatic number is infinite. Indeed, Theorem 1.1 part (i) with $a=b=c=1$ is what you want.
mathworker21's user avatar
3 votes

Topology of directed graph $G$ with non-singular adjacency matrix

Well, if $V=\{1,\ldots,n\}$, $(a_{ij})_{1\leqslant i,j\leqslant n}$ is the adjacency matrix, and it is non-singular, then its determinant (considered as a sum over permutations) has a non-zero term $\...
Fedor Petrov's user avatar
3 votes
Accepted

Topology of directed graph $G$ with non-singular adjacency matrix

There is an edge emanating from any vertex of $G$ because otherwise the corresponding row (or column, according to our convention for forming the adjacency matrix) would be zero. Label the vertices as ...
KhashF's user avatar
  • 2,722
1 vote

Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?

It seems that the answer is negative. A graph $G$ is a co-comparability graph if its complement is a comparability graph. The comparability graphs of posets of dimension 2 are exactly the ...
Vinicius dos Santos's user avatar
1 vote

Complexity of maximum weight-sum matching for cycle graphs

With inspiration from the comments I arrived at the following idea: the maximum weight matching on the cycle is converted to a maximum weight matching on a path that is generated by splitting a vertex,...
Manfred Weis's user avatar
  • 12.6k
1 vote

Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?

For random graphs, there are algorithms that are efficient on average. See for example A fast algorithm on average for solving the Hamilton Cycle problem by Michael Anastos and the references therein. ...
Timothy Chow's user avatar
  • 78.3k
0 votes

Efficient Hamiltonian cycle algorithms for graph classes

Even though the Hamilton path problem is NP-hard, in practice it is usually easy. An efficient algorithm has been known for 50 years. It is "A Search Procedure for Hamilton Paths and Circuits.&...
Frank Rubin's user avatar
0 votes

Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?

The most efficient exact algorithm for finding Hamilton paths and circuits is "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21 (Oct. 1974), pp 576-580; DOI: 10.1145/321850....
Frank Rubin's user avatar
0 votes

Interpreting positive semidefinite matrix as a graph

One characterization of semidefinite positive matrices among symetric matrices is that all their principal minors are positive. The determinant of the adjacency matrix of a graph has a graph-theoritic ...
Hugo MTV's user avatar
  • 188
3 votes

Why do we get a connected 2-regular graph?

The construction makes $U$ the Cayley graph associated to an abelian group $G$ and a pair $\pm g$ of elements of $G$.(*) In such a graph all the components are cycles of the same length, namely the ...
Noam D. Elkies's user avatar
6 votes
Accepted

Chromatic number of the insert-and-shift graph on $S_n$

$\mathbf G_n$ contains the complete graph $K_n$. Consider the set of all permutations where the elements $1,\dots, n-1$ are in the usual order in the sense that $\sigma(1) < \dots < \sigma(n-1)$,...
Will Sawin's user avatar
  • 137k
4 votes

What is this Ramsey problem?

A good reference is Radziszowski's article Small Ramsey Numbers, which gets updated as new results are proven. In particular, this refers to basically all known Ramsey style results. The ones you're ...
David White's user avatar
  • 29.8k
4 votes

A question related to "Locally Sidorenko" type problem

If I understand your question correctly, you are asking if there is a sparse graph counting lemma assuming only that the graphon is within $o(p)$ to the density $p$ in cut norm; the Lovasz result ...
Terry Tao's user avatar
  • 109k
2 votes
Accepted

Homology of independence complex after removing a vertex

There is a fairly standard splitting technique as suggested in the comment, although not necessarily using $v$. Let $G$ be a graph and $v$ is a simplicial vertex. Let $w$ be any neighbor of $v$. Then ...
Michal Adamaszek's user avatar
0 votes

Isometric path cover number of the 2 dimensional grid graph

Assume you have $a$ increasing paths (where both coordinates non-strictly increase) and $b$ decreasing ones. We may assume that all of them start and finish at the vertices of the square. Now perform ...
Ilya Bogdanov's user avatar
2 votes
Accepted

Do the dual graphs of hyperplane arrangements admit Hamiltonian paths?

Already in the plane there are arrangements such that the longest path in their dual covers roughly at most $2/3$ of the regions, therefore they are not Hamiltonian. The reason is that the dual graph ...
Jan Kyncl's user avatar
  • 5,981

Top 50 recent answers are included