Newest questions tagged graph-theory - MathOverflow most recent 30 from www.2874565.com 2019-07-18T21:50:46Z http://www.2874565.com/feeds/tag?tagnames=graph-theory&sort=newest http://www.creativecommons.org/licenses/by-sa/3.0/rdf http://www.2874565.com/q/336450 0 Distance between colored rooted graphs Dreamer123 http://www.2874565.com/users/137903 2019-07-18T19:07:25Z 2019-07-18T19:53:16Z <p><a href="https://i.stack.imgur.com/RCtiH.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/RCtiH.png" alt="enter image description here"></a></p> <p><a href="https://i.stack.imgur.com/HpClG.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/HpClG.png" alt="enter image description here"></a></p> <p>My question is what is the rough meaning of <span class="math-container">$\alpha_{1,2}$</span>?</p> <p>I think of it in this way: Consider two balls one is around <span class="math-container">$o_1$</span> <span class="math-container">$B_{G_1}(o_1,[r])$</span> in the first graph and the other <span class="math-container">$B_{G_2}(o_2,[r])$</span> is around <span class="math-container">$o_2$</span> in the second graph. vary r until the following happens:</p> <ol> <li>You found an isomorphism <span class="math-container">$\phi$</span> between the 2 rooted graphs</li> <li>The distance between the colouring of each vertex in <span class="math-container">$B_{G_1}$</span> and the colouring of its isomorphic vertex in the second graph is bounded by <span class="math-container">$\frac{1}{r}$</span></li> </ol> <p>Is this a correct interpretation? if not then why and how can I think about it?</p> http://www.2874565.com/q/336379 3 Bayesian Networks and Polytree Bremen http://www.2874565.com/users/143236 2019-07-18T05:42:48Z 2019-07-18T05:42:48Z <p>I am a bit puzzled by the use of polytree to infer a posterior in a Bayesian Network (BN). </p> <p>BN are defined as <em>directed acyclic graphs</em>. A <em>polytree</em> is DAG whose underlying undirected graph is a tree. It is known that if a BN is a polytree, exact inference algorithms such a belief propagation can be efficiently applied. If a BN is not a polytree, one may have to use approximate inference algorithms to avoid the potential non-convergence of a belief propagation algorithm. </p> <p>First, I don't understand why BNs should be treated as polytrees. A BN is a DAG <em>by definition</em>, so why one should use polytree to describe BNs?</p> <p>Second, using polytrees seems to degrade the original topology of the BN. If a BN (which is a DAG) is not a polytree, then it is considered to have cycles. It is highly confusing (many research papers on the topic often refer to <em>cyclic BN</em>, where it should be, I believe, <em>a non-polytree BN</em>). Why isn't it possible to use the structure of a BN (<em>i.e.</em>, knowledge about the directed edges) to create exact inference algorithms for non-polytree BNs? It seems that the common message-passing algorithms do not use these topological information, which may explain the poor performance/in-feasibility of exact inference on non-polytree BN. </p> <p>If someone knows enough to answer these questions, I would be glad to have some hints. I really do not understand why the DAG structure of BNs seems to be ignored. </p> http://www.2874565.com/q/336330 11 When is the poset of acyclic orientations of a graph a lattice? David E Speyer http://www.2874565.com/users/297 2019-07-17T16:06:09Z 2019-07-18T14:04:21Z <p><span class="math-container">$\def\inv{\mathrm{inv}}\def\Acyc{\mathrm{Acyc}}$</span>Let <span class="math-container">$G$</span> be a graph whose vertices are numbered <span class="math-container">$\{ 1,2, \ldots, n \}$</span>. Given an orientation <span class="math-container">$\omega$</span> of <span class="math-container">$G$</span>, define the inversions of <span class="math-container">$\omega$</span>, written <span class="math-container">$\inv(\omega)$</span>, to be the set of edges <span class="math-container">$(i,j)$</span> with <span class="math-container">$i&lt;j$</span>, which are oriented <span class="math-container">$i \leftarrow j$</span>. Define one orientation <span class="math-container">$\omega_1$</span> to be <span class="math-container">$\leq$</span> another orienation <span class="math-container">$\omega_2$</span> iff <span class="math-container">$\inv(\omega_1) \subseteq \inv(\omega_2)$</span>. Obviously, the set of all orientations of <span class="math-container">$G$</span> form a boolean lattice in this way. </p> <p>Let <span class="math-container">$\Acyc(G)$</span> be the set of acyclic orientations of <span class="math-container">$G$</span>. Restricting the above partial order to <span class="math-container">$\Acyc(G)$</span> makes <span class="math-container">$\Acyc(G)$</span> into a poset. </p> <blockquote> <p>What is known about when <span class="math-container">$\Acyc(G)$</span> is a lattice?</p> </blockquote> <p>Some thoughts below:</p> <hr> <p><span class="math-container">$\bullet$</span> If <span class="math-container">$G$</span> is the complete graph <span class="math-container">$K_n$</span>, this is the weak order on <span class="math-container">$S_n$</span>, known to be a lattice.</p> <p><span class="math-container">$\bullet$</span> We could ask more strongly when the obvious surjection <span class="math-container">$\Acyc(K_n) \to \Acyc(G)$</span> is a map of lattices or, in other words, if <span class="math-container">$\Acyc(G)$</span> is a quotient of <span class="math-container">$\Acyc(K_n)$</span>. This can be studied using Nathan Reading's classification of quotients of weak orders (see <a href="https://arxiv.org/abs/1405.6904" rel="nofollow noreferrer">Reading, Section 4</a>). The answer is that, if <span class="math-container">$i&lt;j&lt;k$</span>, and <span class="math-container">$(i,k)$</span> is an edge of <span class="math-container">$G$</span>, then <span class="math-container">$(i,j)$</span> and <span class="math-container">$(j,k)$</span> must also be edges of <span class="math-container">$G$</span>. However, this strong condition is not necessary to make <span class="math-container">$\Acyc(G)$</span> into a lattice. Note that <span class="math-container">$\Acyc(F)$</span> will be a lattice for any forest <span class="math-container">$F$</span>, and a tree with <span class="math-container">$\geq 3$</span> edges will not obey the above condition.</p> <p><span class="math-container">$\bullet$</span> <span class="math-container">$\Acyc(G)$</span> is the regions of the graphical hyperplane arrangement coming from <span class="math-container">$G$</span>, see Björner, Edelman and Ziegler, "<a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1036875" rel="nofollow noreferrer">Hyperplane arrangements with a lattice of regions</a>" and Reading's Chapter 9, "Lattice Theory of the Poset of Regions" in <a href="https://link.springer.com/book/10.1007%2F978-3-319-44236-5" rel="nofollow noreferrer">Lattice Theory: Special Topics and Applications</a> for relevant background. So we can phrase this questions as "when do the regions of a graphical hyperplane arrangement form a lattice"? </p> <p><span class="math-container">$\bullet$</span> An example of a graph where this does NOT hold is the one with edge set <span class="math-container">$\{ (1,2), (2,4), (1,3), (3,4) \}$</span>. The elements <span class="math-container">$1 \to 2 \to 4 \to 3 \leftarrow 1$</span> and <span class="math-container">$1 \to 2 \to 4 \leftarrow 3 \to 1$</span> have no join.</p> http://www.2874565.com/q/336294 3 Martingales and intersection of random walks Kcafe http://www.2874565.com/users/16976 2019-07-17T06:51:20Z 2019-07-18T13:41:16Z <p>Let <span class="math-container">$G=(V,E)$</span> be a graph with <span class="math-container">$n$</span> vertices. Consider a pair of independent simple random walks <span class="math-container">$(X,Y)$</span> on the graph, each of length <span class="math-container">$L$</span> starting from a node <span class="math-container">$v \in V$</span>. We denote a length-<span class="math-container">$L$</span> random walk <span class="math-container">$X$</span> as a tuple in <span class="math-container">$V^L$</span>, as <span class="math-container">$(X_1,\ldots, X_L)$</span>. Now consider an estimate of number of intersections in such a pair of random walks, given by <span class="math-container">\begin{align} T (X,Y)= \sum_{j=1}^L \sum_{k=1}^L \mathbb{I}_{\{ X_j = Y_k\}} \end{align}</span> where <span class="math-container">$\mathbb{I}_{\{\cdot\}}$</span> is the indicator function of the event <span class="math-container">$\{\cdot\}$</span>. My question is can the random variable <span class="math-container">$T(X,Y)$</span> be represented as a martingale (plus some reminder terms) ?</p> http://www.2874565.com/q/336154 1 Beck-Fiala Discrepency Type Results for Arbitrary Graph Labelings Raj Raina http://www.2874565.com/users/143106 2019-07-15T07:06:54Z 2019-07-15T08:04:37Z <p>Suppose we have a graph <span class="math-container">$G$</span> on <span class="math-container">$n$</span> vertices <span class="math-container">$x_1 , \dots, x_n$</span> attached with weights of values from <span class="math-container">$1$</span> to <span class="math-container">$n$</span>. We will write <span class="math-container">$\text{weight}(x_i)$</span> as simply <span class="math-container">$x_i$</span> and let <span class="math-container">$\text{diff}(G) = \min _{(x_i,x_j) \in E(G)} |x_i - x_j|$</span>. Then, what is</p> <p><span class="math-container">$$\max \text{diff}(G)$$</span></p> <p>across all permutations <span class="math-container">$(x_1,\dots , x_n)$</span> of <span class="math-container">$[n]$</span>?</p> <p>For example, if <span class="math-container">$\text{diam}(G) = 1$</span> i.e. <span class="math-container">$G=K_n$</span> then the answer is of course <span class="math-container">$1$</span>. Diameter, here, seems like a natural consideration, as does edge density or regularity. </p> <p>Another example, if <span class="math-container">$n$</span> is even and <span class="math-container">$G$</span> is a perfect matching, then we reduce to the analysis problem of finding</p> <p><span class="math-container">$\max \min ( |x_1 - x_2|, \dots , |x_{n-1}-x_n|)$</span></p> <p>across all permutations <span class="math-container">$(x_1,\dots , x_n)$</span> of <span class="math-container">$[n]$</span>.</p> <p>Since our sample space is finite, we know that <span class="math-container">$\max \text{diff}(G) &gt; E[\text{diff}(G)]$</span>, where the expectation may be able to be computed exactly (as in the case that <span class="math-container">$G$</span> is a perfect matching).</p> <p>Literature results on either of these would be nice, thank you!</p> http://www.2874565.com/q/336104 0 Elusive groups and vertex-transitive graphs user52949 http://www.2874565.com/users/52949 2019-07-14T12:54:20Z 2019-07-14T14:40:28Z <p>This question is pertaining to finite connected vertex-transitive graphs.</p> <p>I recently read <i>"Transitive permutation groups without semiregular subgroup</i>" by Cameron, Giudici, Jones, Kantor, Klin, Maru?i?, Nowitz (<a href="https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/S0024610702003484" rel="nofollow noreferrer">publisher link</a>; <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1920405" rel="nofollow noreferrer">MSN review</a>), where I found the concept of "<i>elusive groups</i>".</p> <p>A permutation group <span class="math-container">$G$</span> acting on a set <span class="math-container">$X$</span> is called <i>elusive</i> if <span class="math-container">$G$</span> is transitive and contains no nontrivial semiregular subgroup (equivalently, no fixed-point-free element of prime order). I understand that transitive subgroups of elusive groups are elusive.</p> <p>My question is: In light of the Polycirculant Conjecture, are the following statements is true?</p> <blockquote> <p>Elusive groups cannot be the <i>full</i> automorphism group of any vertex-transitive graph.</p> </blockquote> <p>or</p> <blockquote> <p>Elusive groups cannot be any transitive subgroup of the <i>full</i> automorphism group of any vertex-transitive graph.</p> </blockquote> <p>P.S. I am trying to understand how an elusive Group is a hindrance towards the Polycirculant Conjecture.</p> <p>(Previously <a href="https://math.stackexchange.com/questions/3291579/elusive-groups-and-vertex-transitive-graphs">posted on MathSE</a>.)</p> http://www.2874565.com/q/336037 2 The graph polynomial of the Total Graph of a Graph vidyarthi http://www.2874565.com/users/100231 2019-07-13T07:26:28Z 2019-07-13T08:25:11Z <p>Consider the <a href="http://mathworld.wolfram.com/TotalGraph.html" rel="nofollow noreferrer">Total Graph</a> (<span class="math-container">$T(G)$</span>) of a graph <span class="math-container">$G$</span> with vertex set <span class="math-container">$V$</span> edge set <span class="math-container">$E=\{(u,v)\}$</span> with Line graph <span class="math-container">$L(G)$</span> and subdivision graph <span class="math-container">$S(G)$</span> (formed by putting a vertex in each edge of the original graph). Consider the graph polynomial <span class="math-container">$P_G=\prod_{(u,v)\in E}(u-v)$</span> of the graph <span class="math-container">$G$</span>. </p> <p>Then, it is easy to see that <span class="math-container">$P_{T(G)}=P_{G}\cdot P_{L(G)}\cdot P_{S(G)}$</span>.</p> <p>Can we use the this polynomial to verify the Total coloring conjecture by establishing that the polynomial <span class="math-container">$P_T(G)$</span> does not lie in the ideal generated by the polynomials <span class="math-container">$u^{\Delta+2}-1\ \ ,u\in V\ \$</span>? Specifically, since the polynomials <span class="math-container">$P_G$</span> and <span class="math-container">$P_{L(G)}$</span> already do not lie individually in the ideals generated by <span class="math-container">$u^ {\Delta+2}-1$</span>, thanks to Brooks and Vizings' theorems; and the graph <span class="math-container">$P(S(G))$</span>, being the polynomial of a bipartite graph, elementarily satisfies the condition. This, coupled with the fact the polynomial ring is an integral domain and the ideal generated by the polynomials <span class="math-container">$u^{\Delta+2}-1\ \ ,u\in V\ \$</span> is a prime ideal (I think) should give us the desired result, right? Are there any overlooked facts here? Thanks beforehand.</p> http://www.2874565.com/q/336029 2 Mod $2$ of $\#PM(G)$ for arbitrary G? Turbo http://www.2874565.com/users/10035 2019-07-12T22:11:35Z 2019-07-13T07:22:06Z <p>Permanent mod <span class="math-container">$2$</span> of biadjacency gives polynomial time algorithm of <span class="math-container">$\#PM(G)\mod 2$</span> of perfect matchings of bipartite graph. Is there a similar efficient strategy for general graphs?</p> http://www.2874565.com/q/335927 1 Embedding a graph in $\mathbb{R}^3$ with partial geometric information pckroon http://www.2874565.com/users/142985 2019-07-11T12:42:00Z 2019-07-11T23:20:31Z <p>I have a connected, sparse, graph (a molecule to be specific) and I'm interested in associating 3D coordinates with the vertices. Here's the kicker: I already have coordinates for none/some/all vertices which are not to be changed. The case of no coordinates I can solve with e.g. MDS, and the case where I have all coordinates is trivial.</p> <p>In addition, I have a length associated with every edge which should be respected (but some distortion is fine). If it helps, I also have information about some (not all) angles and dihedral angles. Finally, all vertices should be separated as much as possible from one another. If need be, you may assume a maximum degree of ~6.</p> <p>I don't expect a fully worked solution, but any pointers to literature would already be greatly appreciated!</p> http://www.2874565.com/q/335875 2 Characterization of nilpotent adjacency matrices [closed] Matthias http://www.2874565.com/users/142955 2019-07-10T17:51:40Z 2019-07-11T01:19:38Z <p>Let <span class="math-container">$\theta$</span> be the adjacency matrix of a simple graph (symmetric and zeros on the diagonal). What is the characterization of those <span class="math-container">$\theta$</span> which satisfy <span class="math-container">$$\theta^2 \equiv 0 \pmod{2}$$</span> i.e. which <span class="math-container">$\theta$</span> are nilpotent of order 2 over <span class="math-container">$\mathbb{Z}_2$</span>?</p> http://www.2874565.com/q/335769 5 Can the corollary of the Ihara¨CBass formula be extended to $u^2 = 1$? Eli4ph http://www.2874565.com/users/142877 2019-07-09T09:00:47Z 2019-07-12T12:19:31Z <p>Suppose there is a finite undirected graph <span class="math-container">$G(V,E)$</span> having <span class="math-container">$n$</span> vertices and <span class="math-container">$m$</span> edges. The non-backtracking matrix <span class="math-container">$B$</span> is indexed by <span class="math-container">$2m$</span> directed edges and defined as <span class="math-container">$$B(a \to b, c \to d) = \delta_{bc} (1 - \delta_{ad}) \, .$$</span> The adjacency matrix <span class="math-container">$A$</span> is defined <a href="https://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow noreferrer">as usual</a>.</p> <p>I learned that the Ihara¨CBass formula was established in the context of graph zeta functions. At present I only make sense of an elementary proof without diving into graph zeta functions. By this proof, I learned that if <span class="math-container">$u^2 \neq 1$</span> then <span class="math-container">$$\det(I-uB) = \left(1-u^2\right)^{m-n} \det\left(I - u A + u^2\left[D-I\right]\right) \, ,$$</span> where <span class="math-container">$D$</span> is the <a href="https://en.wikipedia.org/wiki/Degree_matrix" rel="nofollow noreferrer">degree matrix</a>.</p> <p>As a corollary, all roots of the polynomial <span class="math-container">$\det(B - \lambda I)$</span>, except those being <span class="math-container">$\pm 1$</span>, are roots of the polynomial <span class="math-container">$\det\left(\lambda^2 I - \lambda A + \left[D-I\right]\right)$</span>.</p> <p>For all <a href="http://mathworld.wolfram.com/SimpleGraph.html" rel="nofollow noreferrer">simple graphs</a>, we have <span class="math-container">$\det(D - A) = 0$</span>. But for trees, the non-backtracking matrix has no eigenvalues other than <span class="math-container">$0$</span>, which leads to <span class="math-container">$\det(I - B) = \det(I) = 1$</span>. Thus the polynomial <span class="math-container">$\det\left(\lambda^2 I - \lambda A + \left[D-I\right]\right)$</span> can not be used to search the eigenvalues of <span class="math-container">$B$</span> being <span class="math-container">$1$</span>.</p> <hr> <p>Can the corollary be extended to search the eigenvalues of <span class="math-container">$B$</span> being <span class="math-container">$\pm 1$</span>?</p> <p>The motivation behind this question is to get the <strong>whole</strong> spectrum of the non-backtracking matrix of a graph with a much smaller matrix.</p> http://www.2874565.com/q/335757 3 Induced subgraphs of $\text{Exp}(G, K_2)$ Dominic van der Zypen http://www.2874565.com/users/8628 2019-07-09T05:48:42Z 2019-07-09T22:40:34Z <p>If <span class="math-container">$G, H$</span> are simple, undirected graphs, we define the <em>exponential graph</em> <span class="math-container">$\text{Exp}(G,H)$</span> to be the following graph:</p> <ul> <li>the vertex set is the set of all maps <span class="math-container">$f:V(G)\to V(H)$</span></li> <li>two maps <span class="math-container">$f\neq g: V(G)\to V(H)$</span> form an edge if and only if whenever <span class="math-container">$\{v,w\}\in E(G)$</span> then <span class="math-container">$\{f(v), g(w)\}\in E(H)$</span>.</li> </ul> <p>If <span class="math-container">$G$</span> is any simple, undirected graph, finite or infinite, is there a graph <span class="math-container">$G'$</span> such that <span class="math-container">$G$</span> is isomorphic to an <a href="https://en.wikipedia.org/wiki/Induced_subgraph" rel="nofollow noreferrer">induced subgraph</a> of <span class="math-container">$\text{Exp}(G', K_2)$</span>?</p> http://www.2874565.com/q/335687 0 Random graphs - multiple giant components Thomas Lesgourgues http://www.2874565.com/users/118450 2019-07-08T09:14:52Z 2019-07-08T09:14:52Z <p>For a given random graph, a connected component that contains a finite fraction of the entire graph¡¯s vertices is called giant.</p> <p>A well known result in random graphs is the existence and uniqueness of the giant component in Erdos-Rényi model: if <span class="math-container">$G\in G(n,p)$</span> with <span class="math-container">$p=c/n$</span> and <span class="math-container">$c&gt;1$</span>, then there is a unique giant component of size <span class="math-container">$\zeta$</span>, the smallest positive solution to <span class="math-container">$$1-\zeta=e^{-c\zeta}$$</span>.</p> <p>This result has been generalized in many other settings :</p> <ul> <li>Starting with Molloy and Reed who proved a condition for the existence and uniqueness of a giant component for graph with a given degree sequence, under some technical requirements.</li> <li>Under other requirements by Bollobas and Riordan, or Janson and Luczak.</li> <li>Aiello et al. proved a similar result for Power-Law model.</li> <li>Some years ago, Joos et al. showed a condition for the existence of a giant component for any given degree sequence. The uniqueness is still an open problem (as far as I know).</li> </ul> <p>My question is :</p> <blockquote> <p>Is there any random graph model for which, under some supercritical regime, we do not have the uniqueness of the giant component, but rather multiple giant components with positive probability?</p> </blockquote> <p>I would be quite surprised if there is one. But maybe some preferential attachment model, with a fitness parameter as per the Bianconi¨CBarabási model, or a more general Price's model, might have this property.</p> http://www.2874565.com/q/335606 2 Expander graphs with many 4-cycles user2679290 http://www.2874565.com/users/142777 2019-07-06T22:47:56Z 2019-07-07T06:58:01Z <p>The question is not strictly well-defined. But it goes like this:</p> <blockquote> <p>Could you find an infinite family of graphs <span class="math-container">$G_i$</span>, that are all <span class="math-container">$\epsilon$</span>-expanders, but have many 4-cycles? </p> </blockquote> <p><span class="math-container">$\epsilon$</span> should be as large as possible as well as the number of 4-cycles. The family of graphs should be as wide as possible. </p> <hr> <p>This is the basic question. </p> <p>A trivial good example would be a cartesian graph product <span class="math-container">$G \times H$</span>. The expansion of the product is the maximal <span class="math-container">$\epsilon$</span> of the involved graphs. If we take two <span class="math-container">$d$</span>-regular graphs and we look at 2 paths of the product, then about <span class="math-container">$1/3$</span> of the paths are in <span class="math-container">$4$</span>-cycle.</p> <p>But could it be improved? Could the relation be bounded? </p> <p>If we think in terms of Cayley graphs:</p> <p>Say our graph is <span class="math-container">$\mathrm{Cay}(G,S)$</span> and <span class="math-container">$S$</span> is symmetric. A <span class="math-container">$4$</span>-cycle arises from <span class="math-container">$4$</span> generators <span class="math-container">$a,b,c,d$</span> s.t. <span class="math-container">$ab=cd$</span>. It is trivial if either (<span class="math-container">$c=b$</span> and <span class="math-container">$d=a$</span>) or (<span class="math-container">$c=a$</span> and <span class="math-container">$d=b$</span>). </p> <p>I think many trivial cycles would harm expansion since, by Alon-Roichman theorem, abelian groups are bad expanders. </p> <p>So I think the goal should be to find groups and generator sets that have many non-trivial 4-cycles. </p> http://www.2874565.com/q/335557 5 Do the Odd Cycles of a Graph Define a Matroid? Manfred Weis http://www.2874565.com/users/31310 2019-07-06T08:32:04Z 2019-07-07T22:39:58Z <p>An <a href="https://en.wikipedia.org/wiki/Odd_cycle_transversal" rel="noreferrer">Odd Cycle Transversal</a> is a set of vertices that, when removed from a graph, renders it bipartite. </p> <blockquote> <p><strong>Question:</strong> </p> <p>does the collection of "critical" sets of vertices, whose removal renders a graph bipartite, resemble a <a href="https://en.wikipedia.org/wiki/Matroid" rel="noreferrer">Matroid</a>, i.e. will a greedy strategy yield a critical vertex set of minimal cardinality? </p> <p>I am looking for a proof deciding the matroid property that either affirm the success of the greedy strategy or for a proof of at least the existence of instances, where the greedy strategy doesn't yield a minimal set of vertices whose removal renders the graph bipartite; a concrete counter example would be more than I dare to hope for in that case.</p> </blockquote> <p>By a <em>critical</em> set of vertices, in this context, I mean a set of vertices whose removal renders a graph bipartite, but none of its proper subsets has that property. </p> <p>By the <em>greedy strategy</em> I mean repeatedly removing a vertex that is on a maximal number of odd cycles in the graph resulting from previous greedy vertex deletions. </p> <p>Please note that the question is not as to whether it is efficiently possible to determine the number of odd cycles on which a vertex; it is rather assumed that that information comes from a kind of oracle or whatever celestial being you prefer.</p> http://www.2874565.com/q/335497 4 The list chromatic number of some special toroidal grid graphs Jacob.Z.Lee http://www.2874565.com/users/42816 2019-07-05T11:13:12Z 2019-07-06T09:24:43Z <ul> <li><p>A list-assignment <span class="math-container">$L$</span> to the vertices of <span class="math-container">$G$</span> is the assignment of a list set <span class="math-container">$L(v)$</span> of colours to every vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span>; and a <span class="math-container">$k$</span>-list-assignment is a list-assignment such that <span class="math-container">$|L(v)|\geq k$</span>, for every vertex <span class="math-container">$v$</span>. If <span class="math-container">$L$</span> is a list-assignment to <span class="math-container">$G$</span>, then an <span class="math-container">$L$</span>-colouring of <span class="math-container">$G$</span> is a colouring (not necessarily proper) in which each vertex receives a colour from its own list; </p></li> <li><p>The graph <span class="math-container">$G$</span> is <span class="math-container">$k$</span>-list-colourable, or <em><span class="math-container">$k$</span>-choosable</em>, if it is properly <span class="math-container">$L$</span>-colourable for every <span class="math-container">$k$</span>-list-assignment <span class="math-container">$L$</span> to <span class="math-container">$G$</span>. The chromatic number <span class="math-container">$\chi(G)$</span> of <span class="math-container">$G$</span> is the smallest number <span class="math-container">$k$</span> such that <span class="math-container">$G$</span> is <span class="math-container">$k$</span>-colourable. The <em>list chromatic number</em> <span class="math-container">$\chi_l(G)$</span>, is the smallest number <span class="math-container">$k$</span> such that <span class="math-container">$G$</span> is <span class="math-container">$k$</span>-list-colourable or <span class="math-container">$k$</span>-choosable. </p></li> <li><p>It is evident that <span class="math-container">$\chi_l(G)\geq \chi(G)$</span>, since if <span class="math-container">$k &lt; \chi(G)$</span> then <span class="math-container">$G$</span> is not <span class="math-container">$L$</span>-colourable when every vertex <span class="math-container">$v$</span> of <span class="math-container">$G$</span> is given the same list <span class="math-container">$L(v)$</span> of <span class="math-container">$k$</span> colours.</p></li> </ul> <p>Consider the graph <span class="math-container">$S_n$</span> which has as vertex set the <span class="math-container">$n^2$</span> cells of our <span class="math-container">$n\times n$</span> array with two cells adjacent if and only if they are in the same row or column. The graph <span class="math-container">$S_n$</span> Since any <span class="math-container">$n$</span> cells in a row are pairwise adjacent we need at least <span class="math-container">$n$</span> colors. Furthermore, any coloring with <span class="math-container">$n$</span> colors corresponds to a Latin square, with the cells occupied by the same number forming a color class. Since Latin squares, as we have seen, exist, we infer <span class="math-container">$\chi(S_n) = n$</span>, and the Dinitz problem can be stated as <span class="math-container">$$\chi_l(S_n) = n?$$</span></p> <p>Now we know that the equality holds for all <span class="math-container">$n$</span>. By the solution of Dinitz's problem, we know that the list chromatic number of <span class="math-container">$C_3\Box C_3$</span> is 3, i.e. <span class="math-container">$\chi_l(C_3\Box C_3)=3$</span>.</p> <p>The method of attack for the Dinitz problem is : We have to find an orientation of the graph <span class="math-container">$S_n$</span> with outdegrees <span class="math-container">$d_+(v) ¡Ü n?1$</span> for all <span class="math-container">$v$</span> and which ensures the existence of a kernel for all induced subgraphs.</p> <p>I want to know the <span class="math-container">$\chi_l(C_3\Box C_5)$</span> and <span class="math-container">$\chi_l(C_5\Box C_5)$</span>. I conjecure both of them are 3. </p> <p><a href="https://i.stack.imgur.com/OFFSb.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/OFFSb.png" alt="enter image description here"></a></p> <p>In the above oriented graph <span class="math-container">$C_3\Box C_5$</span>, for all vetex <span class="math-container">$V$</span>, it is easy to see that<br> <span class="math-container">$$deg_-(v)=deg_+(v)=2.$$</span> I verified some of induced subgraph which indeed have a kernel. But I have no idea how to prove that all induced subgraph have a kernel. If someone can give any suggestions or comments, I will appreciate it. Thanks.</p> http://www.2874565.com/q/335387 -1 Correlated tree interval and existence of unary subtree user142657 http://www.2874565.com/users/142657 2019-07-04T00:22:40Z 2019-07-04T00:28:29Z <p>We have a collection of random intervals <span class="math-container">$\{I_{k}:=(X_{k},Y_{k})\}_{k=1}^{\infty}\subset [0,1]$</span> s.t.</p> <ul> <li>For deterministic <span class="math-container">$l_{k}\to 0$</span> we have <span class="math-container">$0&lt;l_{k}^{a_{1}}\leq Y_{k}-X_{k}\leq l_{k}^{a_{2}}$</span>.</li> <li>The endpoints <span class="math-container">$\{X_{k},Y_{k}\}_{k\geq 1}$</span> are all correlated ,even for different k, but their lengths <span class="math-container">$|I_{k}|=Y_{k}-X_{k}, |I_{k+m}|=Y_{k+m}-X_{k+m}$</span> are independent when they don't intersect by a buffer: <span class="math-container">$$Y_{k+m}+\epsilon_{k+m}&lt;X_{k}\text{ or }Y_{k}&lt;X_{k+m}-\epsilon_{k+m},$$</span> where deterministic <span class="math-container">$\epsilon_{k}&gt;0$</span> are decreasing to zero: <span class="math-container">$\epsilon_{k}&gt;\epsilon_{k+1}\to 0$</span>.</li> </ul> <p>Let <span class="math-container">$a_{k,n}:=E[X_{k}X_{n}],b_{k,n}:=E[X_{k}Y_{n}],c_{k,n}:=E[Y_{k}Y_{n}]$</span> be the correlations. </p> <blockquote> <p>P: Our problem is to find the probability of arranging the intervals <span class="math-container">$I_{k}$</span> in [0,1] so that their lengths will be independent of each other.</p> </blockquote> <p>We are not asking for counterexamples. All we ask is whether it reminds you of some framework where this question <strong><em>might</em></strong> be placed in. We will do the rest of the work of figuring it out if and how exactly. Just mention some reference and we will go through it.</p> <p><strong>Attempts</strong></p> <p>1)<em>random tree framework with factorial number of children</em></p> <p>The probability of the first two <span class="math-container">$|I_{1}|,|I_{2}|$</span> being independent (we mean their lengths) is the union of the events </p> <p><span class="math-container">$$v_{1}:=\{Y_{2}+\epsilon_{2}&lt;X_{1}\}\text{ or }v_{2}:=\{Y_{1}&lt;X_{2}-\epsilon_{2}\},$$</span> </p> <p>where <span class="math-container">$v_{1},v_{2}$</span> are the first two vertices. If <span class="math-container">$v_{1}$</span> occurs, then we ask for the probability that <span class="math-container">$|I_{3}|,|I_{1}|$</span> are independent <strong>and</strong> <span class="math-container">$|I_{3}|,|I_{2}|$</span> are independent. So now <span class="math-container">$v_{1}$</span> will have three children vertices <span class="math-container">$v_{1,1},v_{1,2},v_{1,3}$</span>.</p> <p>Similarly, at the kth level a vertex <span class="math-container">$v$</span> will have <span class="math-container">$(k+1)!$</span> number of children.</p> <p>The problem is to find the probability of at least one infinite unary subtree i.e. at least one chain of events/vertices. That will give the probability of non-intersecting (with buffer) intervals.</p> http://www.2874565.com/q/335193 2 What's the full assumption for Laplacian matrix $L=BB^T=\Delta-A$? Nick Dong http://www.2874565.com/users/90343 2019-07-01T11:53:49Z 2019-07-13T09:12:37Z <p>Graph with no-selfloop, no-multi-edges, unweighted.</p> <p><strong>directed</strong></p> <p>For directed graph Adjacency matrix is a non-symmetric matrix <span class="math-container">$A_{in}$</span> considering indegree or <span class="math-container">$A_{out}$</span> considering outdegree. Degree matrix <span class="math-container">$\Delta$</span> is diagonal matrix <span class="math-container">$\Delta=\Delta_{in}+\Delta_{out}$</span>. The diagonal elements are sum of indegree and outdegree. The oriented incidence matrix <span class="math-container">$B_{oriented}$</span>, <span class="math-container">$N\times M$</span>. <span class="math-container">$b_{im}=1$</span> if edge <span class="math-container">$m$</span> start from <span class="math-container">$i$</span>. <span class="math-container">$b_{im}=?1$</span> if edge <span class="math-container">$m$</span> ended to <span class="math-container">$i$</span>. <span class="math-container">$b_{im}=0$</span> otherwise. </p> <p><span class="math-container">$\Delta-A_{in}\neq\Delta-A_{out}\neq B_{oriented}B_{oriented}^T$</span></p> <p><strong>undirected</strong></p> <p>For undirected graph and oriented incidence matrix <span class="math-container">$B_{oriented}$</span> have dimension <span class="math-container">$N\times 2M$</span>. <span class="math-container">$B_{oriented}B_{oriented}^T=2\Delta-2A$</span>. </p> <p>unoriented incidence matrix: <span class="math-container">$b_{im}=1$</span> if link <span class="math-container">$m$</span> incident -- start from <span class="math-container">$i$</span> or end to <span class="math-container">$i$</span>. <span class="math-container">$b_{im}=0$</span> otherwise. <span class="math-container">$B_{unoriented}B_{unoriented}^T=\Delta+A$</span>.</p> <p><strong>Problem</strong></p> <p>When Laplacian matrix <span class="math-container">$L=BB^T=\Delta-A$</span>? Many definitions I saw do not give clear assumption in the context. Say, undirected or directed, oriented or unoriented, <span class="math-container">$A_{in}$</span> or <span class="math-container">$A_{out}$</span> or <span class="math-container">$A$</span>? or whatever ... ?</p> <p>Any references would be greatly appreciated. Thank you.</p> <p><strong>EDIT</strong></p> <p>The reference which make me confused is <code>2011, P.V. Mieghem, Graph Spectra for Complex Networks</code> <strong>Chapter 2 Algebraic graph theory</strong> P14. <strong>2.</strong> <strong>The relation between adjacency and incidence matrix is given by the admittance matrix or Laplacian <span class="math-container">$Q=BB^T=\Delta-A$</span></strong></p> <p><strong>EDIT2</strong></p> <p><a href="https://i.stack.imgur.com/gdiZ3.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/gdiZ3.png" alt="enter image description here"></a></p> <h2>1. adjacency matrix</h2> <p>unweighted, nomultiple-edges <span class="math-container">$A$</span>, <span class="math-container">$N\times N$</span>, noselfloop <span class="math-container">$a_{ii}=0$</span></p> <h3>1.1 directed</h3> <p><span class="math-container">$A=\begin{pmatrix} 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1\\ 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\ 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0\\ 1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \end{pmatrix}$</span></p> <h3>1.2 undirected</h3> <p><span class="math-container">$A=\begin{pmatrix} 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 1\\ 1 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 1\\ 1 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0\\ 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 1\\ 1 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \end{pmatrix}$</span></p> <h2>2. incidence matrix <span class="math-container">$B$</span>,</h2> <p><span class="math-container">$N\times M$</span>, <span class="math-container">$M$</span> are edges. lexicographically ordered. </p> <h3>2.1 directed</h3> <p><span class="math-container">$N\times M$</span>, <span class="math-container">$N=6$</span>, <span class="math-container">$M=9$</span>,</p> <p><span class="math-container">$e_1=1\rightarrow 2$</span>, <span class="math-container">$e_2=1\rightarrow 3$</span>, <span class="math-container">$e_3=1\leftarrow 6$</span>, </p> <p><span class="math-container">$e_4=2\rightarrow 3$</span>, <span class="math-container">$e_5=2\leftarrow 5$</span>,<span class="math-container">$e_6=2\rightarrow 6$</span>, </p> <p><span class="math-container">$e_7=3\rightarrow 4$</span>, </p> <p><span class="math-container">$e_8=4\leftarrow 5$</span>,</p> <p><span class="math-container">$e_9=5\leftarrow 6$</span></p> <p><span class="math-container">$$B_{oriented}=\begin{pmatrix} 1 &amp; 1 &amp; -1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\ -1 &amp; 0 &amp; 0 &amp; 1 &amp; -1 &amp; 1 &amp;0 &amp; 0 &amp; 0\\ 0 &amp; -1 &amp; 0 &amp; -1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; -1 &amp; -1 &amp; 0\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; -1\\ 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; -1 &amp; 0 &amp; 0 &amp; 1 \end{pmatrix}$$</span></p> <h3>2.2 undirected</h3> <p><strong><em>(oriented)</em></strong> <span class="math-container">$N\times 2M$</span></p> <p><span class="math-container">$N=6$</span>, <span class="math-container">$M=18$</span>, </p> <p><span class="math-container">$e_1=1\rightarrow 2$</span>, <span class="math-container">$e_2=1\leftarrow 2$</span>, <span class="math-container">$e_3=1\rightarrow 3$</span>, </p> <p><span class="math-container">$e_4=1\leftarrow 3$</span>, <span class="math-container">$e_5=1\rightarrow 6$</span>, <span class="math-container">$e_6=1\leftarrow 6$</span>, </p> <p><span class="math-container">$e_7=2\rightarrow 3$</span>, <span class="math-container">$e_8=2\leftarrow 3$</span>, <span class="math-container">$e_9=2\rightarrow 5$</span>, </p> <p><span class="math-container">$e_{10}=2\leftarrow 5$</span>, <span class="math-container">$e_{11}=2\rightarrow 6$</span>, <span class="math-container">$e_{12}=2\leftarrow 6$</span>, </p> <p><span class="math-container">$e_{13}=3\rightarrow 4$</span>, <span class="math-container">$e_{14}=3\leftarrow 4$</span>, </p> <p><span class="math-container">$e_{15}=4\rightarrow 5$</span>, <span class="math-container">$e_{16}=4\leftarrow 5$</span>, </p> <p><span class="math-container">$e_{17}=5\rightarrow 6$</span>, <span class="math-container">$e_{18}=5\leftarrow 6$</span></p> <p><span class="math-container">$$B_{oriented}=\begin{pmatrix} 1 &amp; -1 &amp; 1 &amp; -1 &amp; 1 &amp; -1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\ -1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; -1 &amp; 1 &amp; -1 &amp; 1 &amp; -1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; -1 &amp; 1 &amp; 0 &amp; 0 &amp; -1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; -1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; -1 &amp; 1 &amp; 1 &amp; -1 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; -1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; -1 &amp; 1 &amp; 1 &amp; -1 \\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; -1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; -1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; -1 &amp; 1\\ \end{pmatrix}$$</span></p> <p><span class="math-container">$$(oriented)~b_{im}= \begin{cases} 1, &amp; \text{if link e_m=i\rightarrow j} \\ -1, &amp; \text{if link e_m=i\leftarrow j} \\ 0, &amp; \text{otherwise} \end{cases}$$</span></p> <p><strong><em>(unoriented)</em></strong> <span class="math-container">$N\times M$</span></p> <p><span class="math-container">$e_1=1 - 2$</span>, <span class="math-container">$e_2=1 - 3$</span>, <span class="math-container">$e_3=1 - 6$</span>, </p> <p><span class="math-container">$e_4=2 - 3$</span>, <span class="math-container">$e_5=2 - 5$</span>,<span class="math-container">$e_6=2 - 6$</span>, </p> <p><span class="math-container">$e_7=3 - 4$</span>, </p> <p><span class="math-container">$e_8=4 - 5$</span>,</p> <p><span class="math-container">$e_9=5 - 6$</span></p> <p><span class="math-container">$$B_{unoriented}=\begin{pmatrix} 1 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\ 1 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1 &amp;0 &amp; 0 &amp; 0\\ 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 0\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 1\\ 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 \end{pmatrix}$$</span></p> <p><span class="math-container">$$(unoriented)~b_{im}= \begin{cases} 1, &amp; \text{if link e_m=i - j incident} \\ 0, &amp; \text{otherwise} \end{cases}$$</span></p> <h2>3. degree matrix</h2> <p><span class="math-container">$\Delta_{ii} =deg(i) = \sum_j A_{ij}$</span>. <span class="math-container">$\Delta_{ij}=0$</span>, <span class="math-container">$i\neq j$</span></p> <h3>3.1 directed</h3> <p><span class="math-container">$\begin{pmatrix} 2£«1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\ 0 &amp; 2£«2 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 1£«2 &amp; 0 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 0 &amp; 0£«2 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 2£«1 &amp; 0\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 2£«1 \end{pmatrix}$</span></p> <h3>3.2 undirected</h3> <p><span class="math-container">$\begin{pmatrix} 3 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\ 0 &amp; 4 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 3 &amp; 0 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 0 &amp; 2 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 3 &amp; 0\\ 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 3 \end{pmatrix}$</span></p> <h2>4. Laplacian matrix</h2> <h3>4.1 directed</h3> <p><span class="math-container">$B_{oriented}B_{oriented}^T$</span> </p> <p><span class="math-container">$\begin{pmatrix} 3 &amp; -1 &amp; -1 &amp; 0 &amp; 0 &amp; -1\\ -1 &amp; 4 &amp; -1 &amp; 0 &amp; -1 &amp; -1\\ -1 &amp; -1 &amp; 3 &amp; -1 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; -1 &amp; 2 &amp; -1 &amp; 0\\ 0 &amp; -1 &amp; 0 &amp; -1 &amp; 3 &amp; -1\\ -1 &amp; -1 &amp; 0 &amp; 0 &amp; -1 &amp; 3 \end{pmatrix}$</span></p> <h3>4.2 undirected</h3> <p><strong><em>(oriented)</em></strong></p> <p><span class="math-container">$B_{oriented}B_{oriented}^T=2\Delta -2A$</span></p> <p><span class="math-container">$\begin{pmatrix} 6 &amp; -2 &amp; -2 &amp; 0 &amp; 0 &amp; -2\\ -2 &amp; 8 &amp; -2 &amp; 0 &amp; -2 &amp; -2 \\ -2 &amp; -2 &amp; 6 &amp; -2 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; -2 &amp; 4 &amp; -2 &amp; 0 \\ 0 &amp; -2 &amp; 0 &amp; -2 &amp; 6 &amp; -2 \\ -2 &amp; -2 &amp; 0 &amp; 0 &amp; -2 &amp; 6 \end{pmatrix}$</span></p> <p><strong><em>(unoriented)</em></strong></p> <p><span class="math-container">$B_{unoriented}B_{unoriented}^T=\Delta + A$</span></p> <p><span class="math-container">$\begin{pmatrix} 3 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 1\\ 1 &amp; 4 &amp; 1 &amp; 0 &amp; 1 &amp; 1\\ 1 &amp; 1 &amp; 3 &amp; 1 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 1 &amp; 2 &amp; 1 &amp; 0\\ 0 &amp; 1 &amp; 0 &amp; 1 &amp; 3 &amp; 1\\ 1 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 3 \end{pmatrix}$</span> </p> http://www.2874565.com/q/335072 7 Correspondence between matrix multiplication and a graph operation of Lovasz David Roberson http://www.2874565.com/users/18606 2019-06-29T10:02:26Z 2019-06-30T14:26:44Z <p>In his book "Large networks and graph limits" (available online here: <a href="http://web.cs.elte.hu/~lovasz/bookxx/hombook-almost.final.pdf" rel="nofollow noreferrer">http://web.cs.elte.hu/~lovasz/bookxx/hombook-almost.final.pdf</a>), Lovasz describes a multiplication operation (he calls it concatenation) on "bi-labeled graphs". An <span class="math-container">$(m,n)$</span> bi-labeled graph is a graph in which some vertices are labeled with the left labels <span class="math-container">$1, \ldots, m$</span>, and some are labeled with the right labels <span class="math-container">$1, \ldots, n$</span>. The left and right label <span class="math-container">$i$</span> are distinguished. A vertex is allowed to have more than one left and/or right labels assigned to it.</p> <p>The concatenation operation of Lovasz (definition begins on page 85 of the above link), is as follows. If <span class="math-container">$G$</span> is a <span class="math-container">$(m,n)$</span> bi-labeled graph and <span class="math-container">$H$</span> is a <span class="math-container">$(n,k)$</span> bi-labeled graph, then the concatenation <span class="math-container">$G \circ H$</span> is the <span class="math-container">$(m,k)$</span> bi-labeled graph obtained from the disjoint union of <span class="math-container">$G$</span> and <span class="math-container">$H$</span> by identifying the vertex of <span class="math-container">$G$</span> with right label <span class="math-container">$i$</span> with the vertex of <span class="math-container">$H$</span> with left label <span class="math-container">$i$</span> for all <span class="math-container">$i = 1, \ldots n$</span>, and then forgetting these labels, but retaining the left labels of <span class="math-container">$G$</span> and the right labels of <span class="math-container">$H$</span>.</p> <p>If it is not clear how this corresponds to matrix multiplication, consider the following. Fix a graph <span class="math-container">$K$</span>. For any <span class="math-container">$(m,n)$</span> bi-labeled graph <span class="math-container">$G$</span>, define the <span class="math-container">$K$</span>-homomorphism matrix of <span class="math-container">$G$</span> as the matrix <span class="math-container">$M^{G \to K}$</span> whose rows/columns are indexed by <span class="math-container">$m$</span>-tuples/<span class="math-container">$n$</span>-tuples of vertices of <span class="math-container">$K$</span> such that its <span class="math-container">$(u_1, \ldots, u_m),(v_1, \ldots, v_n)$</span>-entry is equal to the number of homomorphisms from <span class="math-container">$G$</span> to <span class="math-container">$K$</span> that map the vertex with left label <span class="math-container">$i$</span> to <span class="math-container">$u_i$</span> and the vertex with right label <span class="math-container">$j$</span> to <span class="math-container">$v_j$</span> for all <span class="math-container">$i,j$</span>. One can check that <span class="math-container">$M^{G \circ H \to K} = M^{G \to K}M^{H \to K}$</span>.</p> <p>It is unlikely, to say the least, that Lovasz was not aware of this correspondence between concatenation and matrix multiplication, but I could not find any explicit mention of this in the book or elsewhere. Admittedly I have not read the entire book in detail yet, but I have looked through it for mention of this.</p> <p>Does anyone know if this correspondence is explicitly spelled out anywhere? Either in the book or an article somewhere?</p> http://www.2874565.com/q/335002 3 Polynomial Graph Isomorphism from Star System Reconstruction? joro http://www.2874565.com/users/12481 2019-06-28T14:09:06Z 2019-06-28T15:45:56Z <p>Confusion is possible, but two papers and a simple graph transformation imply Graph Isomorphism is polynomial, which is an open problem.</p> <p>The closed neighborhood of a vertex in a graph is sometimes called the ¡°star¡± of the vertex. The ¡°star system¡± of a graph is then the multi-set of closed neighborhoods of all the vertices of the graph and the Star System problem is the problem of deciding whether a given system of sets is a star system of some graph</p> <p>According to <a href="https://cs.uwaterloo.ca/research/tr/1977/CS-77-04.pdf" rel="nofollow noreferrer">paper1 p.20</a> reconstructing the graph from its star system is GI-complete.</p> <p>According to a <a href="https://sites.cs.ucsb.edu/~daniello/papers/StarSystem.pdf" rel="nofollow noreferrer">paper2 p.3 On the Complexity of Reconstructing H-free Graphs from their Star Systems</a>, <span class="math-container">$C_4$</span>-free or <span class="math-container">$C_3$</span>-free graphs can be reconstructed from their star systems.</p> <p>There is isomorphism preserving graph transformation (given in paper1) <span class="math-container">$G \to G'$</span> where <span class="math-container">$G'$</span> is chordal and hence <span class="math-container">$C_4$</span> free. The transformation is <span class="math-container">$V(G')=V(G) \cup E(G)$</span>. In <span class="math-container">$G'$</span> add a clique of <span class="math-container">$V(G)$</span> and for <span class="math-container">$u,v \in E(G)$</span> add the edges <span class="math-container">$((u,v),u),((u,v),v)$</span>. <span class="math-container">$G'$</span> is <span class="math-container">$C_4$</span>-free, chordal and split. </p> <p>For <span class="math-container">$C_3$</span>-free graph just take the subdivision of <span class="math-container">$G$</span>, which is bipartite and triangle free.</p> <blockquote> <p>Does this prove GI is polynomial?</p> </blockquote> http://www.2874565.com/q/334997 1 A regular independence induced graph in a $\Delta+1$ coloring vidyarthi http://www.2874565.com/users/100231 2019-06-28T12:49:42Z 2019-06-28T12:49:42Z <p>Consider any regular graph <span class="math-container">$G$</span> with order <span class="math-container">$n$</span> and size <span class="math-container">$E$</span> and maximum degree <span class="math-container">$\Delta$</span>. Now, we give a <span class="math-container">$\Delta+1$</span> coloring to the vertices such that each vertex and its neighbors receive distinct colors. </p> <p>Consider a color class of independent vertices in such a coloring. If we remove the color class, then do we have a regular subgraph with with maximum degree <span class="math-container">$\Delta-1$</span>? </p> <p>I think yes. It is easily seen to be true in the case of complete graphs. It can also be extended, I think, to graphs with <span class="math-container">$\Delta\ge\frac{n}{2}$</span>, since each color class in such a coloring would have at most <span class="math-container">$2$</span> vertices. But, given any regular graph, is the claim true? Thanks beforehand.</p> http://www.2874565.com/q/334936 3 Asymptotic formula for the number of connected graphs Aidan Rocke http://www.2874565.com/users/56328 2019-06-27T16:27:40Z 2019-07-03T16:51:19Z <p>It can be shown that the set of graphs with <span class="math-container">$N$</span> vertices <span class="math-container">$G_N$</span> has cardinality: </p> <p><span class="math-container">$$\lvert G_N \rvert = 2^{N \choose 2} \tag{1}$$</span></p> <p>Recently, I wondered how much bigger <span class="math-container">$\lvert G_N \rvert$</span> is compared to the number of graphs with <span class="math-container">$N$</span> vertices that are path-connected, <span class="math-container">$PC_N$</span>. </p> <p>If we denote the set of Hamiltonian paths by <span class="math-container">$H_N$</span> we can easily show that: </p> <p><span class="math-container">$$H_N \subset PC_N \tag{2}$$</span></p> <p>and by Stirling's approximation: </p> <p><span class="math-container">$$\lvert H_N \rvert = N! \sim \sqrt{2\pi N} \big(\frac{N}{e}\big)^N \tag{3}$$</span></p> <p>and therefore <span class="math-container">$\lvert PC_N \rvert$</span> must grow exponentially fast. </p> <p>Now, I'm curious about asymptotic formulas for <span class="math-container">$\lvert PC_N \rvert$</span> and I'm fairly confident that for large <span class="math-container">$N$</span>: </p> <p><span class="math-container">$$\frac{\lvert PC_N \rvert}{\lvert G_N \rvert} \leq e^{-N} \tag{4}$$</span></p> <p>but I suspect that a proof for this statement would be fairly subtle. </p> <p><strong>Note:</strong> I didn't make use of a computer before formulating this hypothesis but in retrospect I should have analysed the connectivity of random graphs, as suggested by Olivier Fouquet. This would have given me more insight into the problem. </p> http://www.2874565.com/q/334758 7 Understanding Gillman's proof of the Chernoff bound for expander graphs Ella Shar http://www.2874565.com/users/128183 2019-06-25T10:04:59Z 2019-07-06T22:44:16Z <p>My question is about the proof of Claim 1 in this paper: <a href="https://pdfs.semanticscholar.org/eae4/a397e716b677e79187ce51ab5dc1f6c3a34d.pdf" rel="noreferrer">Gillman (1993)</a>. At the end of the proof, the author says:</p> <blockquote> <p>The matrix product <span class="math-container">$U^\top\sqrt{D^{-1}}(P+(\mathrm{e}^x-1)B(0)-\mu I)\sqrt{D}U$</span>, which is equal to <span class="math-container">$(D'-\mu I)(I+(D'-\mu I)^{-1}(\mathrm{e}^x-1)D'U^\top D_A U)$</span>, is singular. Therefore,</p> <p><span class="math-container">\begin{align*} 1&amp;\leq \lVert (D'-\mu I)^{-1}(\mathrm{e}^x-1)D'U^\top D_A U \rVert_2 \\ &amp;\leq \frac{1}{\mu-\lambda_2}(\mathrm{e}^x -1). \end{align*}</span></p> <p>(The first inequality uses the continuity of the function <span class="math-container">$\lambda_2(y)$</span>.) </p> </blockquote> <p>I understand why the two expressions at the beginning are equal and I understand the second inequality, but I do not understand the first inequality and also why the matrix product is singular.</p> <p>Let me provide the definitions so you can avoid reading the whole paper. There is a weighted undirected graph <span class="math-container">$G=(V, E, w)$</span> where <span class="math-container">$w_{ij}=0$</span> if <span class="math-container">$\{i,j\}\notin E$</span>. Denote <span class="math-container">$w_i:=\sum_j w_{ij}$</span>. Let <span class="math-container">$P$</span> denote the transition matrix, so <span class="math-container">$P_{ij}:=\frac{w_{ij}}{w_i}$</span>. Denote by <span class="math-container">$\lambda_2$</span> the second largest eigenvalue of <span class="math-container">$P$</span> and by <span class="math-container">$\epsilon:=1-\lambda_2$</span> the spectral gap. Next, let <span class="math-container">$M$</span> be the weighted adjacency matrix <span class="math-container">$M_{ij}:=w_{ij}$</span>. Let <span class="math-container">$A$</span> be a set of vertices and <span class="math-container">$\chi_A$</span> be an indicator function. Some more definitions are:</p> <p><span class="math-container">\begin{align*} &amp;E_r:=\operatorname{diag}(\mathrm{e}^{r\chi_A}) &amp; &amp;P(r):=PE_r \\ &amp;D:=\operatorname{diag}(\frac{1}{w_i}) &amp; &amp;S:=\sqrt{D}M\sqrt{D} \\ &amp;S_r:=\sqrt{DE_r}M\sqrt{DE_r} &amp; &amp; B(r):=\frac{1}{\mathrm{e}-1}(P(r+1)-P(r)) \end{align*}</span></p> <p>Moreover, since <span class="math-container">$S$</span> is unitarily diagonalizable, there exist a unitary matrix <span class="math-container">$U$</span> and a diagonal matrix <span class="math-container">$D'$</span> such that <span class="math-container">$D'=U^\top SU$</span>. Furthermore, there exists a diagonal matrix <span class="math-container">$D_A$</span> such that <span class="math-container">$B(0)=PD_A$</span>.</p> <p>Define <span class="math-container">$\lambda(r)$</span> to be the largest eigenvalue of <span class="math-container">$P(r)$</span> and <span class="math-container">$\lambda_2(r)$</span> to be its second largest eigenvalue. As before, <span class="math-container">$\epsilon_r := \lambda(r)-\lambda_2(r)$</span> is the spectral gap.</p> <p>In Claim 1 the author lets <span class="math-container">$0\leq x\leq r$</span> be some number. He also defines <span class="math-container">$\mu&lt;\lambda(x)$</span> to be any other eigenvalue of <span class="math-container">$P(x)$</span>. At the end of the proof, we are only interested in <span class="math-container">$\mu&gt;\lambda_2$</span>.</p> <p>Some other facts are:</p> <p><span class="math-container">\begin{align*} &amp;\lVert D' \rVert_2 = \lVert D_A \rVert_2 = 1 &amp; &amp;D'=U^\top\sqrt{D^{-1}}P\sqrt{D}U \\ &amp;P(0)=P &amp; &amp;\lambda(0)=1 &amp; &amp;\lambda_2(0)=\lambda_2 \\ &amp;P=\sqrt{D}S\sqrt{D^{-1}} &amp; &amp;P(r)=\sqrt{DE_r^{-1}}S_r\sqrt{E_rD^{-1}} \end{align*}</span></p> <p>I hope I didn't miss anything relevant. Thank you for your help.</p> http://www.2874565.com/q/334756 2 Proving a theorem on coloring a peculiar graph vidyarthi http://www.2874565.com/users/100231 2019-06-25T09:49:53Z 2019-06-25T17:20:17Z <p>Consider the graph formed by <span class="math-container">$k$</span> cliques of order <span class="math-container">$k$</span>, any two cliques sharing at most one point in common. Now, by <a href="https://core.ac.uk/download/pdf/82722509.pdf" rel="nofollow noreferrer">Szekeres-Wilf theorem</a>, I think the graph should be <span class="math-container">$k$</span> colorable, as any connected induced subgraph would have at least one vertex with degree <span class="math-container">$k-1$</span>(for otherwise, the number of cliques would exceed <span class="math-container">$k$</span>). </p> <p>Any counterexamples in this case? Thanks beforehand.</p> http://www.2874565.com/q/334736 4 Hamiltonian paths on the space of graphs Aidan Rocke http://www.2874565.com/users/56328 2019-06-25T05:53:48Z 2019-06-26T04:18:42Z <p><strong>Disclaimer:</strong> I am not a professional graph theorist. </p> <h2>Motivation:</h2> <p>Let's consider the set <span class="math-container">$G_N$</span> of graphs with <span class="math-container">$N$</span> vertices where the vertices are assumed to be distinguishable. This set may correspond to the state space of a biological network whose connectivity varies over time or the set of potential social networks among a community of <span class="math-container">$N$</span> individuals. </p> <p>The cardinality of <span class="math-container">$G_N$</span> is given by: </p> <p><span class="math-container">$$\lvert G_N \rvert = \sum_{k=0}^{ N \choose 2} { { N \choose 2} \choose k} = 2^{{ N \choose 2}} \tag{1}$$</span> </p> <p>I observed that <span class="math-container">$\lvert G_N \rvert$</span> very quickly becomes astronomical: </p> <p><span class="math-container">$$\forall N &gt; 50, \lvert G_N \rvert &gt; 10^{368} \tag{2}$$</span></p> <p>which is many times greater than the number of atoms in the universe. For this reason, I wondered whether there might be a natural way to organise these graphs. One approach that occurred to me was to think of 'Hamiltonian paths' on the space of graphs.</p> <h2>Question:</h2> <p>If <span class="math-container">$G^k_N \subset G_N$</span> denotes the set of graphs with <span class="math-container">$N$</span> vertices with exactly <span class="math-container">$k$</span> edges: </p> <p><span class="math-container">$$\lvert G^k_N \rvert = { { N \choose 2} \choose k} \tag{3}$$</span></p> <p>my question is whether we can index the elements of <span class="math-container">$G^k_N$</span> so we have <span class="math-container">$G^k_N = \{\Gamma_i \}_{i=1}^{{ { N \choose 2} \choose k}}$</span> and <span class="math-container">$\Gamma_i$</span> and <span class="math-container">$\Gamma_{i \pm 1}$</span> differ by at most one edge i.e. all edges are the same except one which is relocated. </p> <p>We can think of this as a Hamiltonian path because there is an edge between each element of <span class="math-container">$G^k_N$</span> and each element of <span class="math-container">$G^k_N$</span> occurs exactly once. </p> <p><strong>Note:</strong> For <span class="math-container">$G^k_N$</span> where <span class="math-container">$k\in \{0,1,{ N \choose 2}-1,{ N \choose 2} \}$</span> this proposition is certainly true. </p> http://www.2874565.com/q/334692 0 Latent Dirichlet allocation and properties of digamma function sunxd http://www.2874565.com/users/74610 2019-06-24T14:16:16Z 2019-06-27T09:32:21Z <p>In the paper Blei, D. M., Ng, A. Y., &amp; Jordan, M. I. (2003). Latent Dirichlet Allocation. Journal of Machine Learning Research, 3(4¨C5), 993¨C1022. <a href="http://www.jmlr.org/papers/volume3/blei03a/blei03a.pdf" rel="nofollow noreferrer">http://www.jmlr.org/papers/volume3/blei03a/blei03a.pdf</a></p> <p>let <span class="math-container">$\frac{\partial L}{\partial \gamma_i} = \psi^{'}(\gamma_i)(\alpha_i + \sum_{n=1}^N \phi_{ni} - \gamma_i) - \psi^{'}(\Sigma_{j=1}^k \gamma_j)\sum_{j=1}^k(\alpha_j + \sum_{n=1}^N \phi_{nj} - \gamma_j) = 0$</span> yields <span class="math-container">$\gamma_i = \alpha_i + \Sigma_{n =1}^{N}\phi_{ni}$</span> (eqn. (17) in the paper's appendix or eqn.(7) in the paper's major part) </p> <p>where, <span class="math-container">$\gamma_i$</span> is the variational Dirichlet parameter that governs the multinomial probability <span class="math-container">$\sum_{n=1}^N\phi_{ni} = 1$</span> (<span class="math-container">$N$</span> is the number of words in a document). see eqn(4) in the paper. <span class="math-container">$\alpha$</span> is the model Dirichlet parameter. <span class="math-container">$\psi$</span> is the digamma function. <span class="math-container">$L$</span> is the lower bound of the likelihood function.</p> <p>This is equivalent to say that <span class="math-container">$\psi^{'}(\Sigma_{j=1}^k \gamma_j)\sum_{j=1}^k(\alpha_j + \sum_{n=1}^N \phi_{nj} - \gamma_j)$</span> is zero.</p> <p>so either <span class="math-container">$\psi^{'}(\Sigma_{j=1}^k \gamma_j)$</span> is zero or <span class="math-container">$\sum_{j=1}^k(\alpha_j + \sum_{n=1}^N \phi_{nj} - \gamma_j)$</span> is zero</p> <p>but which one is zero? And why?</p> <p>clues: in Figure 6, which is the description of the algorithm, </p> <p><span class="math-container">$\gamma$</span> initialized to be for document <span class="math-container">$i$</span>, <span class="math-container">$\gamma_i = \alpha_i + N/k$</span>? where <span class="math-container">$k$</span> is the number of topics.</p> <p>and <span class="math-container">$\phi_{ni}$</span> for the <span class="math-container">$i$</span>th document is initialized to be <span class="math-container">$\phi_{ni} = 1/k$</span> , in this case <span class="math-container">$\sum_{j=1}^k(\alpha_j + \sum_{n=1}^N \phi_{nj} - \gamma_j) = 0$</span> holds since <span class="math-container">$(\alpha_j + \sum_{n=1}^N \phi_{nj} - \gamma_j) = 0$</span> holds for each document <span class="math-container">$j$</span>, but this is just initialization.</p> <p>in the iteration of the algorithm in Figure 6, <span class="math-container">$\phi_{ni}$</span> is normalized to be sum up to 1 which means <span class="math-container">$(\alpha_j + \sum_{n=1}^N \phi_{nj} - \gamma_j) = (\alpha_j + 1 - \gamma_j)$</span>, this seems not to be zero?</p> http://www.2874565.com/q/334657 12 Is there an algorithm to compute a Belyi map for the Riemann surface? SamMar http://www.2874565.com/users/125645 2019-06-23T22:52:01Z 2019-06-25T00:16:03Z <p>Let <span class="math-container">$y^2=x^5-x-1$</span> 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 <span class="math-container">$\{0,1,\infty\}$</span>. </p> <p>In my attempts to do this by hand, I get ramification at 4 points and, subsequently, using Shabat polynomial will skyrocket the degree of the map. Is there a way to avoid increasing the degree to thousands or hundreds? I have <span class="math-container">$\beta=h\circ g\ \circ f$</span>, where <span class="math-container">$f$</span> is projection on <span class="math-container">$x$</span>, <span class="math-container">$g=x^5-x-1$</span> and <span class="math-container">$h=\frac{( 12500 x + 18750 x^2 + 12500 x^3 + 3125 x^4)}{-2869}$</span>. <span class="math-container">$\beta$</span> gives ramification at four points <span class="math-container">$\{0,1, \infty, \frac{3125}{2869}\}$</span>. Also, it is possible to use <span class="math-container">$g=x^5-x$</span> with different <span class="math-container">$h$</span>, but the Shabat polynomial will still be of very big degree....</p> <p>After some work, I have obtained maps: <span class="math-container">$f$</span> projection on <span class="math-container">$x$</span> ramified at five roots of <span class="math-container">$x^5-x-1$</span>, <span class="math-container">$g(z)=z^5-z$</span> ramified at <span class="math-container">$\pm \frac{4}{5\sqrt[4]{5}}$</span>, <span class="math-container">$h=z^4$</span> ramified at <span class="math-container">$0$</span>. As a result <span class="math-container">$\beta=h\circ g\circ f$</span> is ramified at <span class="math-container">$\{0, \frac{256}{3125}, 1, \infty\}$</span>, which is slightly better. Using Shabat map <span class="math-container">$\frac{m}{m+n}=\frac{256}{256+2869}$</span> gives <span class="math-container">$\alpha(z)=\frac{(m+n)^{m+n}}{m^mn^n}z^m(1-z)^n=\frac{(3125)^{3125}}{256^{256} 2869^{2869} }z^{256}(1-z)^{2869}$</span>. The resulting map <span class="math-container">$\alpha\circ\beta$</span> is of huge degree....</p> http://www.2874565.com/q/334648 3 Strong chromatic index of some cubic graphs EGME http://www.2874565.com/users/130113 2019-06-23T18:45:20Z 2019-06-26T16:57:49Z <blockquote> <p><strong>Edit 2019 June 26</strong> New computer evidence forces us to revise our guesses relating strong chromatic index and girth</p> <p><strong>Edit 2019 June 25</strong> Some mistakes have been corrected. Question 2 has changed.</p> <p><strong>Additional information</strong> Additional information is provided regarding small graphs with high strong chromatic index.</p> </blockquote> <p>...</p> <blockquote> <p><strong>Definition</strong> (somewhat informal) A <em>strong edge <span class="math-container">$k$</span> coloring</em> of a cubic (3-regular) graph is a proper <span class="math-container">$k$</span> coloring of its edges so that for each edge, the four edges adjacent to it are colored differently. The <em>strong chromatic index</em> <span class="math-container">$\chi_S(G)$</span> of a cubic graph <span class="math-container">$G$</span> is the smallest number <span class="math-container">$k$</span> for which <span class="math-container">$G$</span> has a strong edge <span class="math-container">$k$</span> coloring.</p> </blockquote> <p>Andersen, in <a href="https://i.stack.imgur.com/BGLe2.png" rel="nofollow noreferrer">1</a>, showed that if <span class="math-container">$G$</span> is a sub-cubic graph (a graph of max degree 3), then <span class="math-container">$\chi_S(G)\le 10$</span>. In the same paper, he asks (the question is attributed to Faudree, Gyárfás, Schelp, and Tuza):</p> <blockquote> <p><strong>Andersen-Faudree-Gyárfás-Schelp-Tuza question, 1992</strong> Is there is a constant <span class="math-container">$m$</span> such that if a cubic graph <span class="math-container">$G$</span> is such that the girth <span class="math-container">$g(G)$</span> of <span class="math-container">$G$</span> is at least <span class="math-container">$m$</span>, then <span class="math-container">$\chi_S(G)=5$</span>?</p> </blockquote> <p>This question is highly significant, as the truth of it would imply the truth of several notorious (cycle double cover, Berge-Fulkerson) graph theoretical conjectures for all (cubic) graphs of large enough girth.</p> <p>As a bit of background information to our question ahead, some (as yet very incomplete) computer investigations would seem to indicate that for bridgeless <span class="math-container">$G$</span>:</p> <blockquote> <p><strong>Guess and estimates</strong></p> <p>1) if <span class="math-container">$g(G)\ge 5$</span> then <span class="math-container">$\chi_S(G)\le 7$</span>*; </p> <p>2) In order for <span class="math-container">$\chi_S(G)\le 6$</span> it is needed that <span class="math-container">$g(G)$</span> be at least 11**.</p> <p>3) In order for <span class="math-container">$\chi_S(G)= 5$</span> it is needed that <span class="math-container">$g(G)$</span> be at least 18***. </p> </blockquote> <p>*Regarding the first guess, it is worth noting that the clique number of the square graph of the line graph of the cubic graphs in question, - which determine the strong chromatic index - drops to 5, from greater than 5 in graphs of smaller girth. </p> <p>** Regarding the second estimate, all graphs of girth 9 that have been tested have strong chromatic index at most 6. However, the first (3,10)-cage listed in [2] (a girth 10 graph) turned out to have strong chromatic index of 7 - the graph is called the Harries graph. The computation that determined this took several days on a standard laptop. </p> <p>*** We have verified that the smallest known cubic graph of girth 17 listed in [2] does not have a strong edge 5 coloring, and that the smallest cubic graph of girth 18 in [2] has a strong edge 5 coloring. </p> <p>We are currently trying to establish the strong chromatic index of several graphs of girth larger than 9 listed in [2], and we are also trying to establish whether the smallest cubic graph of girth 19 known and listed in [2] has a strong edge 5 coloring. We will update this post as information is further verified, or refuted - there is much testing that needs be done yet. However, we believe there is a firm basis for our main question (question 1) ahead. Before it, a bit more about graphs of small girth: almost all (bridgeless) graphs can be colored with 8 colors. The picture ahead shows the only exceptions to this with 18 or fewer vertices, with their colorings. The only one requiring ten colors is the fourth one in the list. We believe there aren't any more.</p> <p><a href="https://i.stack.imgur.com/BGLe2.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/BGLe2.png" alt="graphs with strong chromatic index greater than 8"></a></p> <p>Before we pose our question, we need a definition.</p> <blockquote> <p><strong>Definition</strong> Let an <em><span class="math-container">$n$</span>-prismatic</em> graph be a cubic graph obtained by joining two disjoint circuits of order <span class="math-container">$n$</span> with a perfect matching.</p> </blockquote> <p>Our first question is then:</p> <blockquote> <p><strong>Question 1</strong> [main question] Let <span class="math-container">$G$</span> be prismatic of girth at least 4. Is the strong chromatic index of <span class="math-container">$G$</span> at most 8? Moreover, if the girth of <span class="math-container">$G$</span> is greater than 4, then, is the strong chromatic index of <span class="math-container">$G$</span> at most 7? We note that the prism with two triangles has strong chromatic index 9. As always in our posts, the intent of the question is to provide proof or provide a counterexample.</p> </blockquote> <p>The nature of a possible proof of this is almost necessarily algorithmic. An inductive proof of the more general statement that bridgeless graphs of girth at least 4 have strong chromatic index at most 8 seems a bit out of reach at the moment. Indeed, in working with general graphs of girth 4 and finding subgraphs which are strong 8-critical, we have found over a thousand that are not isomorphic, and fairly large. Of course, there are a few that are small and that occur a lot more often. </p> <p>In <a href="https://i.stack.imgur.com/BGLe2.png" rel="nofollow noreferrer">1</a> a linear time algorithm to find a strong coloring with at most 10 colors is given. We would also like to know if:</p> <blockquote> <p><strong>Question 2</strong> Is there a fast (linear time?) and simple algorithm to find a strong edge 9 coloring of a bridgeless cubic graph with 10 or more vertices?</p> </blockquote> <p><a href="https://i.stack.imgur.com/BGLe2.png" rel="nofollow noreferrer">1</a> Andersen, L. D., The strong chromatic index of a cubic graph is at most 10, <em>Discrete Mathematics</em>, 108 (1992) 231-252</p> <p>[2] Royle, G. Cubic Cages, staffhome.ecm.uwa.edu.au/~00013890/remote/cages/index.html#data</p> http://www.2874565.com/q/334613 2 Calculating Minimum Spanning Trees in Very Big Graphs Manfred Weis http://www.2874565.com/users/31310 2019-06-23T09:30:39Z 2019-06-23T09:30:39Z <p>I need to determine Minimum Spanning Trees (MST) of very big complete graphs, whose edgeweights can be calculated from data that is associated with the vertices. </p> <p>In the planar euclidean case, for example, the edgeweights correspond to euclidean distances between points to which the adjacent vertices map; in that case the vertex degree of the MST can't be more than 6 and consequently it would suffice to calculate the MST in the Subgraph <span class="math-container">$S\subseteq G$</span> that is induced by the 6 edges of smallest weight that are adjacent to each vertex, albeit that would be inferior to calculate the MST of the graph that is induced by the Delaunay Triangulation of the pointset. </p> <p>Now my idea would be to assume a reasonable upper bound <span class="math-container">$k$</span> on the degree of vertices of the MSTs of graphs with edgeweights that can be calculated deterministically from information associated with the vertices and take and attempt to calculate the MST in the Subgraph that is induced by the sets of the <span class="math-container">$k$</span> shortest edges adjacent to the individual vertices; that would reduce the storage requirements from <span class="math-container">$O(n^2)$</span> to <span class="math-container">$O(n)$</span>.<br> The case that the vertex degree of an MST is higher than the assumed <span class="math-container">$k$</span> can be detected during the calculation of of the MST and, if a vertex "runs out" of adjacent edges, the next <span class="math-container">$k$</span> of the shortest adjacent edges can be determined in <span class="math-container">$O(n)$</span> time and added to S to keep the algorithm going. </p> <blockquote> <p><strong>Question:</strong> </p> <p>has the problem of determining MSTs in very big graphs, with edgeweights calculated deterministically from data that is associated with the vertices, already been investigated and what are (free) online ressources can be recommended?</p> </blockquote> http://www.2874565.com/q/334567 2 Complexity of weighted fractional edge coloring mo2019 http://www.2874565.com/users/137800 2019-06-22T11:03:23Z 2019-06-22T15:50:39Z <p>Given an edge-weighted multigraph <span class="math-container">$G=(V,E)$</span> with a positive, rational weight function <span class="math-container">$(w(e): e \in E)$</span>, the weighted fractional edge coloring problem (WFECP) is to compute (<span class="math-container">$\min 1^T x$</span> subject to <span class="math-container">$Ax \ge w, x \ge 0$</span>), where <span class="math-container">$A$</span> is the edge-matching incidence matrix of <span class="math-container">$G$</span>. </p> <p><a href="https://doi.org/10.1137/17M1147676" rel="nofollow noreferrer">Recently (2019)</a> it was shown that WFECP can be solved in strongly polynomial time. Their algorithm runs in time <span class="math-container">$O(mn+n^5 \ell^2 \log(n^2\ell))$</span>, where <span class="math-container">$n, m$</span> and <span class="math-container">$\ell$</span> denote <span class="math-container">$|V|, |E|$</span> and number of edges in the underlying graph, respectively. My question is: what exactly are the main new contributions of the above paper for the WFECP problem, compared to the previous literature? </p> <p>From the complexity standpoint, <a href="https://doi.org/10.1109/18.21215" rel="nofollow noreferrer">an earlier paper (1988)</a> already gives a <span class="math-container">$O(n^5)$</span> strongly polynomial time algorithm for WFECP. Is the new algorithm more efficient, or better in some other way, than the previous ones? </p> <p>Also, it's not clear why multigraphs need to be considered - it seems to me that all parallel edges can be replaced with a single edge whose weight is the total of the weights of the parallel edges, so that the multigraphs problem doesn't seem to be strictly more general or difficult than the problem for simple graphs. </p> <p>I do understand the recent paper makes significant new contributions (such as solving the open problem of computing, in strongly polynomial time, the maximum edge density <span class="math-container">$\Gamma_w(G)$</span> in an odd subset of the vertex set). But I was just wondering what the new contributions of this recent paper are regarding the WFECP problem.</p> É½Î÷¸£²Ê¿ìÀÖÊ®·ÖÖÓ

<em id="zlul0"></em>

<dl id="zlul0"></dl>
<div id="zlul0"><tr id="zlul0"><object id="zlul0"></object></tr></div>
<em id="zlul0"></em>

<div id="zlul0"><ol id="zlul0"></ol></div>