Skip to main content
9 votes
Accepted

Joining the $2^k$ points of $\{0,1\}^k$ with the shortest tree

I suspect that the optimum, for a cube of side length $2$, is $2^k \sqrt{3} - 2 \sqrt{3}+2$. Note that the optimum if we use edges of the cube is $2 (2^k-1)$, so this is better by a factor of roughly $...
David E Speyer's user avatar
8 votes
Accepted

*Friendly* coloring of a digraph

Carsten Thomassen (1983) proved that a digraph with minimal out-degree at least 3 has two vertex-disjoint cycles, call them $C_1$, $C_2$ and color black and white respectively. Then proceed as follows:...
Fedor Petrov's user avatar
8 votes

Is a finite lattice determined by its Hasse diagram (as a graph)?

This is still far from true. Consider for example these lattices (just a random example):
Sam Hopkins's user avatar
  • 23.1k
7 votes
Accepted

What determines internalization of graph-structures into the set world?

The answer is yes for equinumerosity (provided...), but no for graphs. Equinumerosity. KM is commonly taken to include the axiom of choice and furthermore the axiom of global choice, and this makes ...
Joel David Hamkins's user avatar
5 votes
Accepted

If $\widehat{\Gamma}$ is a simply connected clique complex then $\mathrm{Out}(A_\Gamma)$ is an infinite group

What about the following tesselation of the sphere? Am I missing something if I say that there are no disconnecting stars nor two distinct vertices such that the link of one is contained in the star ...
AGenevois's user avatar
  • 8,041
5 votes
Accepted

Is every connected edge-swapping graph edge-transitive?

No - consider the vertex-and-edge graph of a truncated cube. Some but not all edges are part of 3-cycles, so this graph is not edge-transitive, but it is clearly edge-swapping.
Noah Schweber's user avatar
3 votes

On the relationship between graph isomorphism and equivalence in ETL workflow dependency graphs

We consider two directed acyclic graphs $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$ representing task dependency structures. Here, $V = \{v_1, v_2, ..., v_n\}$ is the set of vertices (tasks) identical for ...
Anders Hinking's user avatar
3 votes
Accepted

Generate all non-isomorphic caterpillar trees with $n$ vertices

Here is a SageMath code generating caterpillar graphs on $n$ nodes based on enriching a path graph with leaves. As an example it shows all such graphs on 6 nodes.
Max Alekseyev's user avatar
3 votes
Accepted

"Spanning trees" for connected linear hypergraphs

Counterexample. Let $\mathbb N=\{1,2,3,\dots\}$. For $n\in\mathbb N$ let $[n]=\{1,2,\dots,n\}$. Let $V=\mathbb N\times\mathbb N$. For $n\in\mathbb N$ let $e_n=\{n\}\times\mathbb N$ and $f_n=[n]\times\{...
bof's user avatar
  • 12.6k
3 votes
Accepted

Function of eigenvalues of Laplacian matrix

Since the number of edges $e(G)$ equals the trace of Laplacian matrix of $G$ divided by 2, we have $$f(\mu_1,\mu_2,\dots\mu_n) = \frac{\mu_1+\mu_2+\cdots+\mu_n}2.$$
Max Alekseyev's user avatar
2 votes
Accepted

Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs

It is highly unlikely that such a generalization would exist, because the 3-dimensional matching problem is NP-complete, while polynomial identity testing can be solved efficiently using randomized ...
domotorp's user avatar
  • 18.5k
2 votes
Accepted

The perfect matching problem of planar graph

You don't even need that whole 4-block tree stuff; you can read the result directly by contracting the `rest' into vertices. More details: As in the above proof, fix a set $T$ that minimizes $odd(T)-|...
Therese Biedl's user avatar
1 vote

How sensitive are Neural Networks to weight change?

Output of the ReLU network is $$v = \sum_{ij} X_i A_{ij} w^{(1)}_{ij} \cdots w^{(L)}_{ij} $$ where $i$ is the input $j$ is the path and $A_{ij}$ is $1$ if the path is open and $0$ otherwise. Now if ...
Mikko Pitkonen's user avatar
1 vote

Perfect matchings of a regular, uniform, partite hypergraph

For $r = 3$, if we drop the $3$-partite condition, this is RX3C. If we drop $3$-regular, this is 3DM. 3DM is NP-complete, even when the degree is bounded by $3$ (Garey and johnson). We can get $3$-...
caduk's user avatar
  • 221

Only top scored, non community-wiki answers of a minimum length are eligible