New answers tagged

0

This should rather be seen as comment! meanwhile some ideas came to my mind that I'd like to share in hope to provoke answers to my question. $1$st idea: Tweak Prim's MST algorithm start with a single edge while there are undiscovered vertices add to the $\lbrace 1,3\rbrace$-tree the pair $(\lambda_i, u_j).(\lambda_i, u_j)$ of edges of lightest weightsum ...


7

This is a comment, not an answer, but it will be more convenient to post it as an answer. Consider the vertices of $G_n$ as subsets of $[n]=\{1,\dots,n\}$. Observation 1. $\chi(G_n)\ge\left\lfloor\frac{3n}2\right\rfloor+1$. This is because $G_n$ contains a clique of that size, namely, $\varnothing,\{1\},\{2\},\{1,2\},\{1,2,3\},\{1,2,4\},\{1,2,3,4,\},\{1,2,3,...


1

If you have an account in springer you can see here: https://link.springer.com/chapter/10.1007%2F978-1-4615-4819-5_23


4

The paper which actually was Landau's first scientific paper written at the tender age of 18, was published in his Collected Works, vol. 1. In it, he proposes to rank chess players having played a round robin tournament according to an eigenvector of the results matrix . A much more comprehensive analysis of this method with the help of the (then new) Perron-...


9

As pointed out by others, it is not clear what the contents of this lecture are. However, after a quick internet search I did find some older (2018) lecture notes with the same title written by the same professor: http://math.nsc.ru/conference/g2/g2r2/files/pdf/Lecture-8.pdf At the start of these notes, five papers are mentioned. Based on the topic, the ...


2

One can also completely break this key exchange (and a more general key exchange algorithm) using linear algebra. Consider the following key exchange algorithm. Suppose that $\mathcal{A}_{L},\mathcal{B}_{L}$ are sets of $m\times m$-matrices and $\mathcal{A}_{R},\mathcal{B}_{R}$ are sets of $n\times n$-matrices. Let $C$ be a publicly available $m\times n$-...


5

The book Graphs on Surfaces and Their Applications by Sergei K. Lando and Alexander K. Zvonkin From Amazon page: Graphs drawn on two-dimensional surfaces have always attracted researchers by their beauty and by the variety of difficult questions to which they give rise. The theory of such embedded graphs, which long seemed rather isolated, has witnessed the ...


2

Let me elaborate on the use of Pólya enumeration for this problem. Let $G\simeq S_m \times S_n$ act on $X=\{x_{i,j}\colon 1\leq i \leq m, 1\leq j \leq n\}$ via $(\sigma,\pi)\cdot x_{i,j} = x_{\sigma(i),\pi(j)}$, and via this action view $G\subseteq S_{mn}$. For $g\in G$ let $c_i(g)$ be the number of $i$-cycles of $g$ (in this embedding into $S_{mn}$), and ...


8

I believe one of the first paper was: Bacher, Roland; de la Harpe, Pierre; Nagnibeda, Tatiana The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. Fr. 125, No. 2, 167-198 (1997). Zbl 0891.05062 (Sorry, self-promotion). It has been widely cited by subsequent papers on the subject (use MathSciNet or Zentralblatt) I ...


25

No, because almost all numbers have at least $4$ distinct prime factors, making the divisibility graph contain a hypercube and thus be nonplanar.


0

pyMCFSimplex seems to best fit my needs. "It is a free Python port of a Python Wrapper for MCFSimplex. pyMCFimplex is a Python-Wrapper for the C++ MCFSimplex Solver Class from the Operations Research Group at the University of Pisa. MCFSimplex is a piece of software hat solves big sized Minimum Cost Flow Problems very fast through the (primal or dual) ...


0

The following seems to be a counterexample. Let $G$ be the graph consisting of A cyclic graph with $\mathbb{Z}/2 m \mathbb{Z}$ as its set of vertices (in that order); this will be our set $V'$; $m$ copies of $K_4$, with each one having one vertex attached to some $2j\in \mathbb{Z}/2m\mathbb{Z}$ and another vertex attached to $2j+1\in \mathbb{Z}/2m\mathbb{Z}$...


4

This protocol as it is stated is broken using a quotient attack. I am going to explain this technique in as general of a context that I can (this idea should also break generalizations of this protocol). Suppose that $X$ is a set. Let $G,H$ be monoids that act on $X$. Here $G$ acts on $X$ on the left so that $gx\in X$ whenever $g\in G,x\in X$, and $H$ acts ...


9

Yes, this is true and follows from Wagner's theorem. Wagner's theorem asserts that every graph with no $K_5$ minor can be built from $0$-, $1$-, $2$-, and $3$-sums from planar graphs and a fixed $8$ vertex non-planar graph called the Wagner graph. Since the Wagner graph is not $4$-connected, this implies that every $4$-connected graph with no $K_5$ minor ...


2

The answer is false. Let $G$ be the 3-prism and $\varphi$ the coloring shown below. $G$ cannot have a 2-distance vertex 4-coloring. As all pairs of vertices in $G$ have distance either 1 or 2, a 2-distance coloring of $G$ would require 6 colors.


2

The answer is False. Let $G$ be the Möbius ladder on 12 vertices with every edge subdivided, or in SageMath code, >G=Graph('K?AEF@oM?w@o') #Mobius ladder on 12 vertices >G.subdivide_edges(G.edges(),1) $G$ is a subcubic graph. >max(G.degree()) 3 If the line graph of $G$ admits a 2-distance vertex 4-coloring $\psi$ with colors in $\{1,2,3,4\}$, ...


9

In fact the numbers $a_k$ in the various factors $1+a_k$ are multiples of $4$ and typically small ones. $a_k=0$ unless every prime of the form $4m-1$ dividing $k$ occurs to an even power. If so, $$a_k=4(s_1+1)(s_2+1)\cdots (s_i+1)$$ where the $s_j$ are the exponents of the prime divisors of the form $4m+1$. The number given $3^{114}\ 5^{19}\ 13^6\ 17^9$ ...


2

There is at least one published mention of this problem. Two sequences in the Online Encyclopedia of Integer Sequences, A071983 and A071984, are very relevant. The entry for A071983 gives a reference: Ruemmler, Ronald E., "Square Loops," Journal of Recreational Mathematics 14:2 (1981-82), page 141; Solution by Chris Crandell and Lance Gay, JRM 15:...


39

For any $k\in\mathbb N$ let $a_k$ be the number of points on the circle of radius $\sqrt{k}$ (this number may be zero). For any path as in question and for any $k$ between $1$ and $i^2+j^2-1$, there is going to be either none or exactly one of the points on the circle of radius $\sqrt{k}$ around $(i,j)$. As the sequence of points determines the path, this ...


0

Assume that $i<j.$ You can reduce this to the following simpler-looking question: Consider a continuous-time RW on the integers, moving at rate two, started at $k:=j-i$. Let $T$ be the hitting time of $\{0,N\}$ by this walk, also known as as the exit time from $[1,N-1]$. Let $\tau$ denote the hitting time of $\{0,N\}$ by discrete-time random walk. The ...


6

Here is a section on graph theory in A compendium of NP optimization problems by P. Crescenzi and V. Kann.


2

Something to start with. We have $$\Theta(G)=\sum_{\alpha} (-1)^{\alpha}\#G_\alpha=\sum_{\alpha}(-1)^\alpha\sum_U \mathbf{1}(U\,\text{is a component of}\,G_{\alpha}),$$ where $U$ runs over all induced connected subgraphs of $G$. Changing the order of summation, we get $$ \Theta(G)=\sum_U \sum_{\alpha:\, U\,\text{is a component of}\,G_{\alpha}} (-1)^{\alpha}. ...


10

A site dedicated to graph classes, including the computational complexity of associated problems, is https://www.graphclasses.org


7

https://en.wikipedia.org/wiki/List_of_NP-complete_problems $$ \quad\quad\quad\quad\quad\quad\quad\quad $$


1

This is the "simplest" hypergraph Turán problem, where I put "simplest" in quotes because there is no such thing as a simple hypergraph Turán problem. This paper gives a conjecture that has been proved up to 13 vertices, but I don't have easy access to the paper of Spencer which is supposed to have that proof.


1

There is a proof with a very similar principle than in Petrov's proof. Take an arbitrary coloring. If the property is not respected, you have a vertex $v$ where one of the colors $c_1$ appear strictly over $⌈\frac{d(v)}{k}⌉$, and another color $c_2$ appear less or equal than $⌊\frac{d(v)}{k}⌋$ (or one which appear strictly less than $⌊\frac{d(v)}{k}⌋$ and ...


5

For the case when $G$ is connected, we can argue as follows: Since $\lvert E(G)\rvert=\lvert V(L(G))\rvert$, the inequality $\lvert E(L(G))\rvert<\lvert E(G)\rvert$ can be read as "$L(G)$ has more vertices than edges". Since $L(G)$ is connected as well, it must therefore be a tree. In particular, $L(G)$ cannot contain cycles. Therefore, $G$ ...


2

If we pass to the complement, this is just a replication. But passing to a complement preserves the class of perfect graphs (a theorem of Lovasz, previously conjecture of Berge).


0

Matchings: the line graph of a matching has no edges. Paths: the line graph of every path of length $k\ge 1$ has $k-1$ edges. Paths might be the only connected graphs with this property, which may be proved by induction as in Gordon Royle's comment.


1

This is a non-answer that's growing a little large for a comment. First, a mathematical statement of a slightly generalised version of the game. The board is a graph. Each player has a starting vertex and a set of goal vertices. At any stage there is a subgraph of marked edges. A legal move for a player is to mark any edge incident on the connected ...


1

The point is that the nature of these two distributions is completely different. The degree distribution is local: in order to find it one one just has to know how the 1-neighbourhoods of vertices look like. The distance distribution is global. Essentially, it measures the dependence of the size of the graph distance spheres on radius, i.e., the growth of ...


1

I think that distance distributions are actually much more interesting and informative than degree distributions of graphs. The reason is that graphs with the same degree distributions can have very different properties, including very different distance distributions. Examples are the Node Duplication model of random graphs and the Barabasi-Albert (...


0

This question is actually equivalent to the distribution of shortest path lengths in random graphs - Mor Nitzan, Eytan Katzav, Reimer Kühn, and Ofer Biham, Distance distribution in configuration-model networks, Phys. Rev. E 93, 062309 (2016). In the case of random regular graphs there is an exact result, which is a Gompertz distribution. The tail ...


Top 50 recent answers are included