Newest questions tagged graph-theory - MathOverflow most recent 30 from www.2874565.com 2019-10-22T06:19:11Z http://www.2874565.com/feeds/tag?tagnames=graph-theory&sort=newest https://creativecommons.org/licenses/by-sa/4.0/rdf http://www.2874565.com/q/344286 -1 Can you create a directed graph on five vertices where each vertex touches every other vertex in one or two moves [on hold] max_178 http://www.2874565.com/users/147505 2019-10-21T14:10:42Z 2019-10-21T14:10:42Z <p>Can you create a directed graph on five vertices where each vertex touches every other vertex in one or two moves.</p> http://www.2874565.com/q/344205 2 How does the complexity of calculating the Permanent imply the NP completeness of directed 3-cycle cover? Manfred Weis http://www.2874565.com/users/31310 2019-10-20T11:02:54Z 2019-10-21T00:43:50Z <p>In their paper <a href="http://wwwhome.math.utwente.nl/~mantheyb/conferences/APPROX2002_BlaeserManthey_3CycleCovers.pdf" rel="nofollow noreferrer">Two Approximation Algorithms for 3-Cycle Covers</a> of Markus Bläser and Bodo Manthey it is stated that: <em>"...deciding whether an unweighted directed graph has a 3-cycle cover is already NP-complete. This follows from the work of Valiant [16] (see also Garey and Johnson [7, GT 13])."</em> </p> <p>However I can't see what of Valiant's paper <a href="https://core.ac.uk/download/pdf/82500417.pdf" rel="nofollow noreferrer">The Complexity of Computing the Permanent</a> should imply the stated NP-completeness; also GT13 <em>Minimum Bottleneck Path Matching</em> of Garey and Johnson seems to have no obvious relation to the stated complexity. </p> <blockquote> <p><strong>Questions:</strong> </p> <ul> <li>why does the NP-Completeness of deciding the existence of a directed vertex-disjoint cycle cover follow from Valiant's complexity result of calculating the Permanent? </li> <li>what is the transformation that demonstrates the equivalence of the Minimum Bottleneck Path Matching and deciding the existence of a directed vertex disjoint 3-cycle cover? </li> </ul> </blockquote> <p>I have already done extensive googling, but could not find anything that could be cited as a proof of the claimed complexity of deciding the existence of a directed vertex-disjoint 3-cycle cover.</p> http://www.2874565.com/q/343734 1 Coloration of an interval graph with constraints [on hold] user147149 http://www.2874565.com/users/147149 2019-10-12T23:28:53Z 2019-10-12T23:28:53Z <p>Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total duration of the tasks corresponding to each color does not exceed a constant <span class="math-container">$W$</span> and there exists, for each color, at least to successive activities where the elapsed time between them is greater than or equal a constant <span class="math-container">$R$</span>.</p> <p>I don't know how to solve this problem or how to transform it to a know problem.</p> http://www.2874565.com/q/343703 0 Algorithmic complexity of deciding the existence of regular $\mathrm{f}$-factors in graphs Manfred Weis http://www.2874565.com/users/31310 2019-10-12T15:00:10Z 2019-10-14T16:11:09Z <p>Finding regular <span class="math-container">$\mathrm{f}$</span>-factors in undirected simple graphs can be reduced to finding a perfect matching by utilizing the gadgets of Tutte or of Lovász and Plummer; there are several algorithms available for bipartite graphs and for general graphs. I have however so far not seen algorithms that implement the necessary and sufficient conditions of Tutte for the existence of a perfect matching. </p> <blockquote> <p><strong>Question:</strong><br> Is calculating a maximal matching the most efficient way of deciding the existence of an <span class="math-container">$\mathrm{f}$</span>-factor, or can the existence of an <span class="math-container">$\mathrm{f}$</span>-factor be decided more efficiently? </p> </blockquote> <p>Update:<br> I just found <a href="https://arxiv.org/abs/1901.10387" rel="nofollow noreferrer">this publication</a> which seems to be related to the question.</p> http://www.2874565.com/q/343607 4 Probability of a vertex being a "degree-celebrity" in a random graph Manfred Weis http://www.2874565.com/users/31310 2019-10-11T04:48:00Z 2019-10-17T15:41:57Z <p>If <span class="math-container">$G(n,p)$</span> is a random graph of the <a href="https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model" rel="nofollow noreferrer">Erdös-Rényi</a> model,<br> what is the probability that <span class="math-container">$\mathrm{deg}(v)\gt\mathrm{deg}(u)\ \forall u\in\mathrm{adj}(v)$</span> </p> <p>Please feel free to relate answers to other models of random graphs.</p> http://www.2874565.com/q/343559 -2 Polya Enumeration to study proper graph colorings vidyarthi http://www.2874565.com/users/100231 2019-10-10T13:11:19Z 2019-10-10T13:11:19Z <p>Can Polya enumeration technique or its modification be used in evaluating the chromatic polynomial of a simple graph?</p> <p>Specifically, we have to ensure that two distinct points have distinct colors if they are adjacent in the simple graph, which is not ensured by the Polya enumeration theorem. I think some modification in the weightings of the colors with respect to the orbits of the action of the automorphism group of the graph may be of some help. What are the complications arising in this? The Polya enumeration is used in the counting of the number of spanning subgraphs, but graph coloring is something that is not usually covered. Thanks beforehand. </p> http://www.2874565.com/q/343342 2 Efficiently computable graph conductance measures user929304 http://www.2874565.com/users/115841 2019-10-07T15:39:45Z 2019-10-11T07:34:49Z <ul> <li>Treating electrical networks from a graph theory point of view, do there exist measures that characterize the overall electrical <a href="https://en.wikipedia.org/wiki/Conductance_(graph)" rel="nofollow noreferrer">conductance</a> of the graph whilst being efficiently computable?</li> </ul> <p>There exists for instance the <a href="http://mathworld.wolfram.com/KirchhoffIndex.html" rel="nofollow noreferrer">Kirchhoff index of a resistor network</a>, which is the sum of resistance distances (effective resistance) taken over all pairs of vertices. This index is e.g. a strictly decreasing function w.r.t addition of edges in the graph. But as a general measure, it does not allow to compare the conductance of two given networks.</p> <p>Another measure of interest might be the <a href="https://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)" rel="nofollow noreferrer">Cheeger constant</a>, which is a quite interesting one, capturing information on whether the flow of current through the network is bottlenecked or not (similar to min-max flow problems). Thus, at this level it does qualify as a measure to compare flow of current across two networks. But computing the Cheeger constant for graphs is known to be a <a href="https://cstheory.stackexchange.com/questions/30762/is-the-cheeger-constant-mathsfnp-hard">NP-hard problem</a>, which means it is not efficiently computable for large networks. </p> <p><em>Admittedly, I am new to the topic of circuit theory in the context of graphs, and I wanted to ask if there are other known measures (possibly inspired from the close analogy between resistor networks and random walks), that allow us to characterize the conductance of a graph.</em> </p> http://www.2874565.com/q/343131 8 Thurston on the Robertson-Seymour theorem Arnaud http://www.2874565.com/users/6325 2019-10-04T08:51:04Z 2019-10-04T08:51:04Z <p>Danny Calegari recounts <a href="https://lamington.wordpress.com/2012/08/22/bill-thurston-1946-2012/#more-1729" rel="noreferrer">here</a> that Bill Thurston "gave one talk explaining his idea of a new proof of (some version of) the Robertson-Seymour theorem" at MSRI in 1996-1997. I could not find it in the extensive video archive of MSRI. </p> <p>Is there any account of his ideas available somewhere (apart from this blog post)? Or perhaps someone who was present in the audience remembers some bits of it?</p> http://www.2874565.com/q/343104 4 Reference for results about planar graphs David Roberson http://www.2874565.com/users/18606 2019-10-03T22:15:51Z 2019-10-06T00:24:53Z <p>A colleague and I are writing a paper in which we need to make use of some basic facts about planar graphs. I would strongly prefer to simply give references for the results if possible, because the proofs themselves are not important to the (already long) paper and I have always been terrible at writing proofs about planar embeddings and related things (so you are sparing any would-be readers as well). Unfortunately I was not able to find references for these specific results and so I thought I would post them here and ask if anyone can provide some references.</p> <p>If you do not know specific references but perhaps know some short, preferably combinatorial, proofs of these results using results for which you do have references, then that may also be helpful.</p> <p>I assume that planar embeddings are polygonal, i.e., edges are embedded as finitely many straight line segments. I cannot assume that my graphs are 3-connected. By <em>facial cycle</em> I mean a cycle of the graph which is the boundary of a face in some planar embedding. Below are the results I am looking for references for:</p> <p><strong>Proposition 1:</strong> Suppose <span class="math-container">$G$</span> is a planar graph with cycle <span class="math-container">$C = u_1, \ldots, u_k$</span>. Let <span class="math-container">$G'$</span> be the graph obtained from <span class="math-container">$G$</span> by adding a new vertex <span class="math-container">$u$</span> adjacent to each <span class="math-container">$u_i$</span>. Then <span class="math-container">$C$</span> is a facial cycle of <span class="math-container">$G$</span> if and only if <span class="math-container">$G'$</span> is planar. Moreover, any planar embedding of <span class="math-container">$G$</span> in which <span class="math-container">$C$</span> is bounding some face <span class="math-container">$F$</span> can be extended to a planar embedding of <span class="math-container">$G'$</span> where <span class="math-container">$u$</span> is embedded in <span class="math-container">$F$</span> and then connected to the vertices <span class="math-container">$u_1, \ldots, u_k$</span>.</p> <p><strong>Proposition 2:</strong> Let <span class="math-container">$G$</span> be a graph and let <span class="math-container">$S \subseteq V(G)$</span>. Then <span class="math-container">$G$</span> has a planar embedding which has a face incident to every vertex of <span class="math-container">$S$</span> if and only if the graph <span class="math-container">$G'$</span> obtained from <span class="math-container">$G$</span> by adding a new vertex <span class="math-container">$s$</span> adjacent to every element of <span class="math-container">$S$</span> is planar. Moreover, any planar embedding of <span class="math-container">$G$</span> in which the vertices of <span class="math-container">$S$</span> are incident to a common face <span class="math-container">$F$</span> can be extended to a planar embedding of <span class="math-container">$G'$</span> where <span class="math-container">$s$</span> is embedded in <span class="math-container">$F$</span> and then connected to every vertex of <span class="math-container">$S$</span>.</p> <p><strong>Proposition 3:</strong> Suppose that <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> are planar graphs with facial cycles <span class="math-container">$C_1 = u^1_1, \ldots, u^1_\ell$</span> and <span class="math-container">$C_2 = u^2_1, \ldots, u^2_k$</span> respectively. Let <span class="math-container">$G'$</span> be the graph obtained from <span class="math-container">$G_1 \cup G_2$</span> by adding edges <span class="math-container">$u^1_1u^2_1, \ldots, u^1_m u^1_m$</span> for some <span class="math-container">$m \le \min\{\ell,k\}$</span>. Then <span class="math-container">$G'$</span> is planar and <span class="math-container">$C' = u^1_m,u^1_{m+1}, \ldots, u^1_\ell, u^1_1, u^2_1,u^2_k,u^2_{k-1},\ldots, u^2_m$</span> is a facial cycle.</p> http://www.2874565.com/q/343004 2 Is this graph problem NP-Hard? dineshdileep http://www.2874565.com/users/27249 2019-10-03T00:05:26Z 2019-10-03T02:46:40Z <p>I had asked this question in <a href="https://math.stackexchange.com/questions/3375396/is-this-graph-problem-np-hard?noredirect=1#comment6946013_3375396">math.se</a> without any success</p> <p>Let <span class="math-container">$A$</span> be the symmetric <span class="math-container">$n\times n$</span> adjacency matrix for a graph where <span class="math-container">$A_{ij}$</span> is the positive edge value between node <span class="math-container">$i$</span> and <span class="math-container">$j$</span> (thus fully connected graph). Among the <span class="math-container">$n-$</span> nodes, let <span class="math-container">$c$</span> be a given node of interest (called a central node in my problem). Define the matrix <span class="math-container">\begin{align} B_{ij}=\begin{cases} 0 &amp;,~~i=j \\ \frac{A_{ij}}{A_{ic}A_{jc}} &amp;,~~\text{otherwise} \end{cases} \end{align}</span> Thus the individual elements are proportional to distance between <span class="math-container">$i$</span> and <span class="math-container">$j$</span> and inversely proportional to distance from the central node. Thus, this term will be high for pairs which are close to central node, but far from each other. I am interested in solving the following optimization problem <span class="math-container">\begin{align} \max_{x_{ij}}\sum_{i,j}x_ix_j&amp;B_{ij} \\s.t.~~\sum_{i=1}^{n}x_i\leq K ~~,&amp;~~x_i\in\{0,1\} \end{align}</span> Intuitively, I need to select <span class="math-container">$K$</span> nodes such that they are as close as possible to the central node yet far apart among themselves?</p> <p>Is this problem studied in literature? Is it NP-Hard? what are the known practical approaches? I am familiar with the Semidefinite formulation of this. I am interested in knowing if there are graph based approaches.</p> http://www.2874565.com/q/342979 5 Random walk on the hypercube with deleted edges RandomWalker http://www.2874565.com/users/146692 2019-10-02T19:21:11Z 2019-10-11T20:43:06Z <p>Let <span class="math-container">$G$</span> be the <span class="math-container">$n$</span>-dimensional boolean hypercube, i.e. the graph on <span class="math-container">$\{0,1\}^n$</span> where two vertices are adjacent iff they differ on exactly one coordinate. Consider a graph <span class="math-container">$G'$</span> obtained by deleting a <span class="math-container">$p$</span> fraction of edges from <span class="math-container">$G$</span> arbitrarily. What is a lower bound on the probability that a <span class="math-container">$t$</span> step random walk on <span class="math-container">$G$</span> (with uniformly random starting vertex and transition at each step) is entirely contained in <span class="math-container">$G'$</span>? I am most interested in the regime where <span class="math-container">$t$</span> is order <span class="math-container">$n$</span> and <span class="math-container">$p$</span> is order <span class="math-container">$\log n /n$</span> and I suspect one should be able to prove a lower bound of the form <span class="math-container">$2^{-pt}$</span>.</p> <p>I can show using small-set expansion on the hypercube that <span class="math-container">$G'$</span> has a connected component of size at least <span class="math-container">$2^{n(1-p)}$</span>, but do not know how to argue about the random walk not leaving the component.</p> http://www.2874565.com/q/342936 20 When can a graph be oriented to form a Hasse diagram of a finite poset? Ethan http://www.2874565.com/users/38626 2019-10-02T11:54:05Z 2019-10-17T21:12:48Z <p>For any finite poset <span class="math-container">$P=(X,\leq)$</span> there is an undirected graph <span class="math-container">$G$</span> underlying the Hasse diagram of <span class="math-container">$P$</span> such that <span class="math-container">$V(G)=X$</span> and <span class="math-container">$E(G)=\{\{u,v\}:u\lessdot v\}$</span>. With that said, is it possible to characterize all these graphs? That is, those graphs which underlie the Hasse diagram of some finite poset? </p> <p>Clearly they must all be triangle free since any orientation of a triangle will result in either a cycle which isn't acyclic or an arc between two vertices and a path of length two between those vertices which isn't transitively reduced. Moreover its easy to see any bipartite graph will fall into this class since if the vertices in an arbitrary graph <span class="math-container">$G$</span> can be partitioned into two independent sets <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> then if we define <span class="math-container">$R=\bigcup_{e\in E(G)}(e\cap X)\times (e\cap Y)$</span> we see <span class="math-container">$P=(X\cup Y,R)$</span> is a poset with a height of one and that <span class="math-container">$G$</span> underlies the Hasse diagram of <span class="math-container">$P$</span>. In fact if for any poset <span class="math-container">$P$</span> we let <span class="math-container">$h(P)$</span> denote the height of <span class="math-container">$P$</span> then whenever a graph <span class="math-container">$G$</span> underlies the Hasse diagram of <span class="math-container">$P$</span> we must have that <span class="math-container">$\chi(G)\leq h(P)+1$</span> as a consequence of the Gallai¨CHasse¨CRoy¨CVitaver theorem. Though despite this class of graphs being closed under edge subdivisions, graphs in this class are not closed under edge contractions which rules out using the graph minor theorem. However because this class of graphs is closed under the removal of edges and vertices (since removing arcs from the Hasse diagram of any finite poset yields another Hasse diagram which is a subposet of its parent) it would still make sense to look for some other type of forbidden subgraph characterization (not necessarily involving minors) of this class. In fact one can prove if we call any digraph a psuedocycle when it is either a directed cycle or if it can be formed by flipping one arc in a directed cycle, then there exists a family of pairwise non-isomorphic graphs <span class="math-container">$\mathcal{F}$</span> where <span class="math-container">$G\in\mathcal{F}$</span> iff the following holds:</p> <p><span class="math-container">$$(1)\text{ Every orientation of }G\text{ contains at least one psuedocycle}$$</span> <span class="math-container">$$(2)\text{ Every proper subgraph of G has an orientation containing no psuedocycles}$$</span></p> <p>Such that any graph can be oriented to form a Hasse diagram of a finite poset iff it has no subgraph isomorphic to an element in <span class="math-container">$\mathcal{F}$</span>. But how can this class of forbiden subgraphs be further simplified? Now I can prove if <span class="math-container">$G$</span> is one of these forbiden subgraphs then <span class="math-container">$G$</span> must be <span class="math-container">$2$</span>-vertex connected and satisfy <span class="math-container">$\chi(G)\geq \text{girth}(G)$</span> though this alone still hardly narrows down what exactly these forbidden subgraphs look like. Is it possible to simplify the above criteria for these forbiden subgraphs? I know the smallest two by order are the triangle graph and the Grötzsch graph, but what are some others? </p> http://www.2874565.com/q/342791 2 Electrode assignment problem in resistive networks user929304 http://www.2874565.com/users/115841 2019-09-30T16:04:37Z 2019-10-08T10:20:33Z <p><strong>Main question</strong></p> <ul> <li>In the context of resistor networks, and particularly purely from a graph theory point of view, is there a consistent way of assigning the two electrode nodes in order to compare the conductivity or equivalently the resistance of two networks?</li> </ul> <p>The intuitive choices might be:</p> <ul> <li><p>Choosing the furthest (graph distance) two nodes in the network and computing the equivalent resistance between those.</p></li> <li><p>Randomly choosing the two nodes and averaging over a certain number of realisations.</p></li> <li><p>Fixing the distance between the measuring (electrode) nodes, therefore, measuring resistance as a function of graph distance. </p></li> </ul> <p>Either of these definitions have an arbitrary aspect to them. For example, if we choose the first definition, then the two networks may have very different diameters, and therefore, we'd be comparing resistances at different distances.</p> <p>For simplicity, we can assume the individual resistors (edge values) to be constant and uniformly distributed. </p> <hr> <p><strong>Context:</strong></p> <p>Generally, for this question one can assume any connected graph of <span class="math-container">$n$</span> nodes and <span class="math-container">$m$</span> edges where each edge is a resistor. Then with the generalized Kirchhoff's laws and assuming Ohm's relation holds, the circuit theory equations in matrix form can be written as follows:</p> <p>The nodal voltages and currents: </p> <p><span class="math-container">$$\psi = (\psi_1, \cdots, \psi_n)^T$$</span> which together with the incidence matrix <span class="math-container">$D$</span>[*] of the graph allows to write the voltages across edges as:</p> <p><span class="math-container">$$V= D^T \psi$$</span> Similarly, for the nodal currents (<span class="math-container">$J$</span>) and currents across edges (I): <span class="math-container">$$J = DI.$$</span></p> <p>With Ohm's law, we have a linear relation between the current and voltage, e.g. current at a given edge <span class="math-container">$x$</span> is given by:</p> <p><span class="math-container">$$I_x = G_k V_x$$</span> where <span class="math-container">$G$</span> is an <span class="math-container">$m$</span> by <span class="math-container">$m$</span> diagonal matrix of conductances (inverse of each value corresponding to resistances) across each edge, which we can assume to be uniformly assigned to <span class="math-container">$1,$</span> so <span class="math-container">$G$</span> is for now an identity matrix. </p> <p>Then given two electrode nodes <span class="math-container">$i$</span> and <span class="math-container">$j,$</span> in order to measure the resistance between them, we can insert a current of <span class="math-container">$1$</span> and <span class="math-container">$-1$</span> at each node respectively with other nodal currents set to zero, and we solve the linear system of form <span class="math-container">$Ax=b$</span> given by <span class="math-container">$DGD^T \psi = J,$</span> which yields <span class="math-container">$\psi.$</span> Having the nodal voltages and currents, we can compute the resistance with <span class="math-container">$R_{i,j}=\frac{\psi_i - \psi_j}{1}.$</span> </p> <p>[*]: Each column of <span class="math-container">$D$</span> corresponds to an edge of the graph and contains exactly one <span class="math-container">$1$</span> at the tail-node of the edge and one <span class="math-container">$-1$</span> at the head-node of the edge.</p> <hr> <p><strong>Re-iterated questions:</strong></p> <ol> <li><p>Given two graphs <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> (each assumed connected), one might e.g. be a transformed version of the other, how should the electrode nodes be assigned in order to consistently compare the conductivity of the two graphs? Are any of my suggestions at the start valid? In other words, is there any way of making statements about the conductivity of two graphs independently of the choice of electrode nodes?</p></li> <li><p>In general, in the context of conductivity of random graphs and random resistor networks, is the dependence of conductivity/resistance on the choice of electrodes a well studied problem? </p></li> </ol> <hr> <p><strong>Addendum:</strong></p> <p>In order to better clarify the specific context of interest and in view of the discussions so far, I write here additional details:</p> <p>I am primarily interested in the case of graphs treated as resistor networks, i.e. simple connected graphs (can be random graphs), given by a vertex set and edge set, where each vertex is circuit junction and each graph edge <span class="math-container">$(i,j)$</span> is a resistor of <span class="math-container">$r_{ij}=1$</span> Ohm. </p> <p>In this context, we can for instance define a metric in terms of the <a href="https://en.wikipedia.org/wiki/Resistance_distance" rel="nofollow noreferrer">effective resistance</a> between two arbitrary vertices, often also called resistance distance between the nodes. And at the level of graphs, we do not have a dimensionality problem, of 2D or 3D that we'd have in the context of uniform continuous bodies (generally <a href="https://en.wikipedia.org/wiki/Simply_connected_space" rel="nofollow noreferrer">simple connected spaces</a>) for which methods such as the vdP as mentioend in the answer below exist for computing their resistivity. </p> <p>Instead, focusing on graphs, we can compute the resistance tensor <span class="math-container">$R_{ij},$</span> by e.g. assuming a homogeneous edge-wise resistance distribution <span class="math-container">$r_{ij}=1$</span> Ohm for all edges <span class="math-container">$(i,j)$</span>, and insert a current <span class="math-container">$I=1$</span>A between two arbitrary nodes and compute the voltage drop across all pairs of vertices yielding the effective resistance <span class="math-container">$R_{ij}$</span> between them (aka the resistance distance between nodes <span class="math-container">$i,j$</span>), as summarised in the <strong>context</strong> section above. But this (i.e. the <span class="math-container">$R_{ij}$</span>'s) is always dependent on the choice of vertices, and I am trying to learn if there exists a measure of resistivity/conductivity for the entire graph, quantifying how conductive/resistive a graph is based on its underlying connectivity structure, and thus providing a means of comparison between different graphs, and irrespective of where on the graph one would place the electrodes. </p> <p>In this regard, I have e.g. found out about the <a href="http://mathworld.wolfram.com/KirchhoffIndex.html" rel="nofollow noreferrer">Kirchhoff index of graphs</a>, which is the sum of the effective resistances across all pairs of vertices, and the <a href="https://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)" rel="nofollow noreferrer">Cheegar constant of graphs</a>, which if I understood correctly, characterizes how "bottlenecked" flow across the graph can become, but given the close analogy to random walks, and confusing terminology (e.g. Cheegar constant is also called <a href="https://en.wikipedia.org/wiki/Conductance_(graph)" rel="nofollow noreferrer"><em>conductance</em> of a graph</a>), I don't know which of these, if any, represent a valid measure of electrical conductivity of the graphs, or if other definitions of <em>graph resistivity</em> exist. </p> http://www.2874565.com/q/342702 8 Connected subgraphs and their sums nan http://www.2874565.com/users/75538 2019-09-28T23:43:03Z 2019-10-21T13:48:12Z <p>Let <span class="math-container">$G=(V,E)$</span> be an undirected graph with <span class="math-container">$|V|\geq 4$</span> such that for any distinct vertices <span class="math-container">$a_1,a_2,b_1,b_2$</span>, there is a path from <span class="math-container">$a_1$</span> to <span class="math-container">$a_2$</span> and a (vertex-)disjoint path from <span class="math-container">$b_1$</span> to <span class="math-container">$b_2$</span>. Assign a nonnegative real number to each vertex in <span class="math-container">$V$</span>. Suppose the sum of these numbers is <span class="math-container">$2s$</span>, and a subset of them has sum exactly <span class="math-container">$s$</span>. What is the largest constant <span class="math-container">$c$</span> for which (regardless of <span class="math-container">$G$</span> and <span class="math-container">$s$</span>) there always exists a subset <span class="math-container">$V'\subseteq V$</span> such that both <span class="math-container">$V'$</span> and <span class="math-container">$V\backslash V'$</span> form connected subgraphs, and the sum of the numbers in <span class="math-container">$V'$</span> belongs to <span class="math-container">$[cs,s]$</span>?</p> <p>The following example shows that <span class="math-container">$c\leq 5/6$</span>: a clique <span class="math-container">$K_5$</span> with one edge <span class="math-container">$e$</span> removed, numbers <span class="math-container">$3,3$</span> on the two vertices adjacent to <span class="math-container">$e$</span>, and <span class="math-container">$2,2,2$</span> on the remaining vertices. Is <span class="math-container">$c=5/6$</span> tight?</p> <p>(It is easy to see that such a constant <span class="math-container">$c$</span> must exist: <span class="math-container">$c=0$</span> works since for any connected graph, its vertices can be partitioned into two parts such that both parts are connected.)</p> http://www.2874565.com/q/342429 2 Edge coloring graphs is in P? vidyarthi http://www.2874565.com/users/100231 2019-09-25T13:20:48Z 2019-09-26T07:55:57Z <p>It is known that there exist polynomial time algorithm to approximate the <a href="https://en.wikipedia.org/wiki/Lov%C3%A1sz_number" rel="nofollow noreferrer">Lovasz number</a> or the supremum of Shannon capacity of graphs. </p> <p>By Vizing's theorem, the graph <span class="math-container">$G$</span> has only two chromatic indices-either its maximum degree (in which case the line graph of <span class="math-container">$G$</span> may be perfect), or one more than it (in which case, the line graph is definitely not perfect). Then, by approximately calculating the lovasz number of the jump graph of <span class="math-container">$G$</span> (complement of the line graph of <span class="math-container">$G$</span>), and, then using the Lovasz sandwich theorem, it must be possible to determine the chromatic index right? Then does this imply that edge coloring is in P( or at least, can approximated in P)? What am I missing here? Thanks beforehand.</p> http://www.2874565.com/q/342426 1 Perfect graphs condition could be weakened? vidyarthi http://www.2874565.com/users/100231 2019-09-25T12:44:32Z 2019-09-25T19:01:48Z <p>The perfect graphs are generally defined as those graphs whose every induced subgraph has its chromatic number equal to its clique number.</p> <p>Now,are there some examples where the clique number of graph equals its chromatic number but some induced subgraph has different clique and chromatic numbers. If so, then for what class of graphs, does the equivalence of chromatic and clique numbers for graphs implies their equivalence for every induced subgraph. Complete graphs, their line graphs, bipartite graphs, their line graphs are such examples. </p> http://www.2874565.com/q/342420 1 Chromatic number of certain graphs with high maximum degree vidyarthi http://www.2874565.com/users/100231 2019-09-25T11:53:58Z 2019-09-30T10:30:43Z <p>Let <span class="math-container">$G$</span> be the graph of even order <span class="math-container">$n$</span> and size <span class="math-container">$\ge\frac{n^2}{4}$</span> which is a Cayley graph on a nilpotent group but not complete. Can the chromatic number of this graph be determined in polynomial time?</p> <p>I suspect such a graph would have chromatic number less than or equal to <span class="math-container">$\frac{n}{2}$</span> if the generating set does not have order <span class="math-container">$2$</span> elements, because we would always find two unique elements non-adjacent to each other. Is this right? Or are there counterexamples? </p> http://www.2874565.com/q/342194 20 Is this representation of Go (game) irreducible? Sebastien Palcoux http://www.2874565.com/users/34538 2019-09-21T20:30:01Z 2019-09-22T08:48:58Z <p>This post is <em>freely</em> inspired by the basic rules of <a href="https://en.wikipedia.org/wiki/Go_(game)" rel="noreferrer">Go (game)</a>, usually played on a <span class="math-container">$19 \times 19$</span> grid graph. </p> <p>Consider the <span class="math-container">$\mathbb{Z}^2$</span> grid. We can assign to each vertex a <em>state</em> "black" (<span class="math-container">$b$</span>), "white" (<span class="math-container">$w$</span>) or "empty" (<span class="math-container">$e$</span>).<br> A <em>state</em> of the grid is a map <span class="math-container">$$\phi: \mathbb{Z}^2 \to \{b,w,e\}.$$</span> The subsets <span class="math-container">$\phi^{-1}(\{b\})$</span> and <span class="math-container">$\phi^{-1}(\{w\})$</span> decompose into <em>connected components</em> <span class="math-container">$c$</span>. Let <span class="math-container">$d(c)$</span> be the <em>number of liberties</em> of <span class="math-container">$c$</span>, i.e. the number of elements of <span class="math-container">$\phi^{-1}(\{e\})$</span> connected to <span class="math-container">$c$</span> by an edge.<br> The following picture on the left shows a white connected component <span class="math-container">$c_1$</span> with number of liberties <span class="math-container">$d(c_1)=8$</span> and a black connected component <span class="math-container">$c_2$</span> with <span class="math-container">$d(c_2) = 5$</span>. On the right, there is a black connected component <span class="math-container">$c_3$</span> with <span class="math-container">$d(c_3)=0$</span>.</p> <p><a href="https://i.stack.imgur.com/S3NYU.png" rel="noreferrer"><img src="https://i.stack.imgur.com/S3NYU.png" alt="enter image description here"></a> <span class="math-container">$\hspace{2cm}$</span> <a href="https://i.stack.imgur.com/Q6vSV.png" rel="noreferrer"><img src="https://i.stack.imgur.com/Q6vSV.png" alt="enter image description here"></a></p> <p>A state <span class="math-container">$\phi$</span> is <em>finite</em> if <span class="math-container">$|\phi^{-1}(\{b,w\})| &lt; \infty$</span>, and is <em>admissible</em> if all its connected components <span class="math-container">$c$</span> have at least one liberty. Let <span class="math-container">$\mathcal{F}$</span> be the set of finite admissible states. Let <span class="math-container">$g \in \mathbb{Z}^2$</span> and consider the map <span class="math-container">$B_g: \mathcal{F} \to \mathcal{F}$</span> such that if <span class="math-container">$\phi(g) \neq e$</span> then <span class="math-container">$B_g(\phi) = \phi$</span>, else <span class="math-container">$B_g(\phi)$</span> is the state made by first putting the vertex <span class="math-container">$g$</span> to the state "black", then removing every white connected component without liberty, then removing every black connected component without liberty (<em>suicide</em> allowed).<br> See the following examples:</p> <p><a href="https://i.stack.imgur.com/JhjQh.gif" rel="noreferrer"><img src="https://i.stack.imgur.com/JhjQh.gif" alt="enter image description here"></a> <span class="math-container">$\hspace{0.7cm}$</span> <a href="https://i.stack.imgur.com/rCD4F.gif" rel="noreferrer"><img src="https://i.stack.imgur.com/rCD4F.gif" alt="enter image description here"></a> <span class="math-container">$\hspace{0.7cm}$</span> <a href="https://i.stack.imgur.com/TxPII.gif" rel="noreferrer"><img src="https://i.stack.imgur.com/TxPII.gif" alt="enter image description here"></a></p> <p>The map <span class="math-container">$W_g$</span> is defined similarly by interchanging black and white. Now, let <span class="math-container">$H$</span> be the Hilbert space <span class="math-container">$\ell^2(\mathcal{F})$</span>. We extend <span class="math-container">$B_g$</span> and <span class="math-container">$W_g$</span> by linearity on <span class="math-container">$H$</span>. The adjoint <span class="math-container">$B^*_g$</span> of <span class="math-container">$B_g$</span> is given by: <span class="math-container">$$B^*_g(\phi) = \sum_{\phi' \in B_g^{-1}(\{ \phi\})} \phi'$$</span> The adjoint <span class="math-container">$W^*_g$</span> of <span class="math-container">$W_g$</span> is given by a similar formula. </p> <p>Let <span class="math-container">$\mathcal{A}$</span> be the <a href="https://en.wikipedia.org/wiki/*-algebra" rel="noreferrer"><span class="math-container">$*$</span>-algebra</a> generated by the set <span class="math-container">$\{B_g,B_g^*, W_g, W_g^* \ | \ g \in \mathbb{Z}^2 \}$</span>.</p> <p><strong>Question</strong>: Is <span class="math-container">$H$</span> an <a href="https://en.wikipedia.org/wiki/Irreducible_representation" rel="noreferrer">irreducible representation</a> of <span class="math-container">$\mathcal{A}$</span>? </p> <p>If yes, this means that the <a href="https://en.wikipedia.org/wiki/Von_Neumann_algebra" rel="noreferrer">von Neumann algebra</a> <span class="math-container">$M:=\mathcal{A}''$</span> equals <span class="math-container">$B(H)$</span>, the algebra of all <a href="https://en.wikipedia.org/wiki/Bounded_operator" rel="noreferrer">bounded operators</a>. Else, what is <span class="math-container">$M$</span>?</p> <p><em>Remark</em>: these questions can be extended to any <a href="https://en.wikipedia.org/wiki/Finitely_generated_group" rel="noreferrer">finitely generated group</a> <span class="math-container">$\Gamma$</span> where the grid becomes its <a href="https://en.wikipedia.org/wiki/Cayley_graph" rel="noreferrer">Cayley graph</a>. It should again be extended to any <a href="https://en.wikipedia.org/wiki/Vertex-transitive_graph" rel="noreferrer">vertex-transitive graph</a>, where for any vertex <span class="math-container">$g$</span>, <span class="math-container">$\Vert B_g \Vert^2$</span> should "intuitively" be <span class="math-container">$2^d$</span> (with <span class="math-container">$d$</span> the degree of the graph). The extension to any <em>connected</em> graph could reveal problems with unbounded operators; to avoid that we can assume the graph to be <a href="https://en.wikipedia.org/wiki/Regular_graph" rel="noreferrer"><span class="math-container">$k$</span>-regular</a> (with <span class="math-container">$k$</span> finite), or at least the degree of valency of the vertices to be bounded.</p> <p>We could experiment these questions on some small finite graphs by brute force with a computer. </p> http://www.2874565.com/q/342038 2 Define a homomorphism of a set of graphs to its power set gete http://www.2874565.com/users/116857 2019-09-19T17:18:32Z 2019-09-19T22:43:23Z <p>Let <span class="math-container">$G$</span> be a simple graph and <span class="math-container">$S$</span> be the set of all sub graphs of <span class="math-container">$G$</span>. Define two operations on <span class="math-container">$S$</span> as: <span class="math-container">$union$</span> of two graphs <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> is, <span class="math-container">$G_1\cup G_2$</span></p> <p><span class="math-container">$=\langle V(G_1)\cup V(G_2), (E(G_1)\cup E(G_2)\rangle$</span> </p> <p>and the graphs <span class="math-container">$intersection$</span> is, <span class="math-container">$G_1\cap G_2$</span></p> <p><span class="math-container">$=\langle V(G_1)\cap V(G_2), (E(G_1)\cap E(G_2)\rangle$</span>. </p> <p>Let <span class="math-container">$P(S)$</span> be the power set of <span class="math-container">$S$</span> and for any two subsets of <span class="math-container">$S$</span> namely, <span class="math-container">$A, B\in P(S)$</span>, define:</p> <p><span class="math-container">$A\sqcup B=\lbrace G_i\cup G_j:~G_i\in A, G_j\in B\rbrace$</span> and </p> <p><span class="math-container">$A\sqcap B=\lbrace G_i\cap G_j:~G_i\in A, G_j\in B\rbrace$</span>. Also, consider a mapping </p> <p><span class="math-container">$f: S\rightarrow P(S)$</span> such that <span class="math-container">$f(empty~ graph)= emptyset$</span> and <span class="math-container">$f( G)=S$</span>.</p> <blockquote> <p>So, how should <span class="math-container">$f$</span> be defined so that it is a homomorphism keeping in mind that every element of <span class="math-container">$S$</span> is a graph while every element of <span class="math-container">$P(S)$</span> is a subset containing graphs?</p> </blockquote> http://www.2874565.com/q/341983 1 Combinatorial equation system with exponentially many equations in quadratic many variables NicoDean http://www.2874565.com/users/63938 2019-09-19T03:58:53Z 2019-09-19T22:12:05Z <p>A certain question on graph theory (about the <a href="http://www.2874565.com/questions/311325/vertex-coloring-inherited-from-perfect-matchings-motivated-by-quantum-physics?noredirect=1&amp;lq=1">existance of graphs with a certain coloring inherited by perfect matchings</a>) can be translated into the satisfiability problem of a certain set of equations (<a href="http://www.2874565.com/a/341885/63938">formulated by Michael Engelhardt</a>).</p> <p>Let <span class="math-container">$X_i$</span> be indexed by an integer <span class="math-container">$1\leq i\leq n$</span>, and <span class="math-container">$x_i \in \{ 0,1,\ldots ,c-1 \}$</span>. We have variables <span class="math-container">$\omega_{X_i,X_j,x_i,x_j} \in \mathbb{C}$</span> (with <span class="math-container">$\omega_{X_j, X_i, x_j, x_i} = \omega_{X_i, X_j, x_i, x_j}$</span>).</p> <p>For a fixed <span class="math-container">$n$</span> and <span class="math-container">$c$</span>, we ask whether there is a set of <span class="math-container">$\omega_{X_i,X_j,x_i,x_j}$</span> which solves the following set of equation for every value of the varibles <span class="math-container">$x_i$</span>:</p> <p><span class="math-container">$$\sum_{m=1}^{n!} \prod_{j=1}^{n/2} \omega_{X_{P^{(m)}(2j-1)}, X_{P^{(m)}(2j)}, x_{P^{(m)}(2j-1)}, x_{P^{(m)}(2j)}} = \prod_{i=1}^{n-1} \delta_{x_i,x_{i+1} }$$</span></p> <p>where <span class="math-container">$P^{(m)}(k)$</span> denotes the <span class="math-container">$k$</span>-th entry in the <span class="math-container">$m$</span>-th permutation of <span class="math-container">$1,2,\ldots ,n$</span>.</p> <p>The only known cases are <span class="math-container">$c=2$</span> for each even <span class="math-container">$n$</span>, and <span class="math-container">$c=3$</span> for <span class="math-container">$n=4$</span>. One solution for <span class="math-container">$c=3$</span> for <span class="math-container">$n=4$</span> is <span class="math-container">$$\omega_{X_1,X_2,0,0}=\frac{1}{8}, \omega_{X_3,X_4,0,0}=\frac{1}{8}$$</span> <span class="math-container">$$\omega_{X_1,X_3,1,1}=\frac{1}{8}, \omega_{X_2,X_4,1,1}=\frac{1}{8}$$</span> <span class="math-container">$$\omega_{X_1,X_4,2,2}=\frac{1}{8}, \omega_{X_2,X_3,2,2}=\frac{1}{8}$$</span> and all other <span class="math-container">$\omega_{X_i,X_j,x_i,x_j}=0$</span>.</p> <blockquote> <p><strong>Question 1:</strong> Does this set of equation have solutions other than <span class="math-container">$(n,c=2)$</span> and <span class="math-container">$(n=4,c=3)$</span>?</p> </blockquote> <p>It seems likely that the answer to this question is no, because</p> <ul> <li>For the special case of <span class="math-container">$\omega_{X_i,X_j,x_i,x_j} \in \mathbb{R_+}$</span>, <a href="http://www.2874565.com/a/267013/63938">Ilya Bogdanov has proved</a> that these are the only solutions, using graph theoretical methods.</li> <li>The number of equations that need to be fulfilled grow as <span class="math-container">$c^n$</span>, while the number of free variables <span class="math-container">$\omega_{X_i,X_j,x_i,x_j}$</span> grow only as <span class="math-container">$c^2\frac{n(n-1)}{2}$</span>.</li> </ul> <p>Even through, no answer is known for any other case.</p> <blockquote> <p><strong>Question 2</strong>: Have you seen any similar or related equation systems or problem in general before?</p> </blockquote> http://www.2874565.com/q/341926 2 Is there a known proof that $R(5,5)\leq 47$ in Ramsey theory? Edwin Karat http://www.2874565.com/users/146022 2019-09-18T16:07:37Z 2019-09-18T16:31:38Z <p>As an application to a model describing graphs with partial information, I found what might be an (as yet unverified) proof that <span class="math-container">$R(5,5)\leq 47$</span>.</p> <p>According to the Dynamic Survey of Ramsey Numbers at <a href="https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1" rel="nofollow noreferrer">https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1</a> that bound is not yet proved. However, I don't know if that survey is up to date.</p> http://www.2874565.com/q/341894 3 Connected hypergraphs Dominic van der Zypen http://www.2874565.com/users/8628 2019-09-18T09:16:13Z 2019-09-18T11:17:57Z <p>We say that a <a href="https://en.wikipedia.org/wiki/Hypergraph" rel="nofollow noreferrer">hypergraph</a> <span class="math-container">$H=(V,E)$</span> is <em>connected</em> if the following condition holds:</p> <blockquote> <p>for all <span class="math-container">$S\subseteq V$</span> with <span class="math-container">$\emptyset\neq S \neq V$</span> there is <span class="math-container">$e\in E$</span> that meets both <span class="math-container">$S$</span> and <span class="math-container">$V\setminus S$</span>, i.e. <span class="math-container">$$S\cap e \neq \emptyset \neq (V\setminus S)\cap e.$$</span></p> </blockquote> <p>Given <span class="math-container">$H=(V,E)$</span> connected, is there <span class="math-container">$E_0\subseteq E$</span> with the following properties?</p> <ol> <li><span class="math-container">$(V,E_0)$</span> is connected, and</li> <li>whenever <span class="math-container">$E'\subseteq E_0$</span> with <span class="math-container">$E'\neq E_0$</span> then <span class="math-container">$(V,E')$</span> is no longer connected.</li> </ol> http://www.2874565.com/q/341688 6 Squared squares and partitions of $K_{nn}$ Aaron Meyerowitz http://www.2874565.com/users/8008 2019-09-16T01:44:51Z 2019-09-16T20:05:11Z <p>This is inspired by a <a href="http://www.2874565.com/questions/340083/a-specific-collection-of-subgraphs-in-k-70-70">recent question</a>.</p> <p>Define a square square sum (<strong>SSS</strong>) of order <span class="math-container">$n$</span> to be any partition <span class="math-container">$$n^2=\sum_1^tc_ii^2 \tag{*}$$</span> of <span class="math-container">$n^2$</span> into square summands. Call it <em>perfect</em> if all <span class="math-container">$c_i \leq 1,$</span> the summands have distinct sizes. </p> <p>This question concerns those SSSs which are achieved by certain decompositions.</p> <p>A <a href="https://en.wikipedia.org/wiki/Squaring_the_square" rel="nofollow noreferrer">squared square</a> is a tiling of of an <span class="math-container">$n \times n$</span> square into smaller integer sided subsquares. If <span class="math-container">$c_i$</span> is the number of <span class="math-container">$i \times i$</span> subsquares then the SSS (*) is achieved. </p> <p>A <span class="math-container">$K_{nn}$</span> <em>decomposition</em> is a partition of <span class="math-container">$K_{nn}$</span> into edge disjoint subgraphs, each being a <span class="math-container">$K_{ii}.$</span> If <span class="math-container">$c_i$</span> is the number of copies of <span class="math-container">$K_{ii}$</span> then the SSS (*) is achieved.</p> <p>If an SSS of order <span class="math-container">$n$</span> is achieved by a squared square it is also achieved by a <span class="math-container">$K_{nn}$</span> decomposition: Index the vertices of <span class="math-container">$K_{nn}$</span> by the rows and columns of the large square. Each <span class="math-container">$i \times i$</span> tile determines a <span class="math-container">$K_{ii}$</span> subgraph.</p> <p>Is the converse true?</p> <blockquote> <blockquote> <p>If a particular SSS (*) is achieved by a <span class="math-container">$K_{nn}$</span> decomposition, is it also achieved by a squared square?</p> </blockquote> </blockquote> <p>I would guess not, but I don't have a counter-example.</p> <p>The motivating question starts with the perfect SSS <span class="math-container">$\sum_1^{24}i^2=70^2$</span> and asks if it can be achieved by a decomposition of <span class="math-container">$K_{70,70}$</span> using one copy of <span class="math-container">$K_{ii}$</span> for each <span class="math-container">$i \leq 24.$</span></p> <p>If there is indeed such a decomposition, then the answer to my question is no because it is known that the smallest perfect squared square has side <span class="math-container">$110.$</span></p> <hr> <p>Here are two alternate viewpoints. I am not sure how much they help so consider them optional.</p> <p>Given an ordering of the vertices from each part of a <span class="math-container">$K_{nn}$</span>, the edges label the <span class="math-container">$n^2$</span> cells of an <span class="math-container">$n \times n$</span> square. This is the correspondence we used to make the reduction from a squared square of order <span class="math-container">$n$</span> to a <span class="math-container">$K_{nn}$</span> decomposition. In the other direction, given a <span class="math-container">$K_{nn}$</span> decomposition with an ordering of vertices, assign each <span class="math-container">$K_{ii}$</span> its own color and transfer these to the cells of an <span class="math-container">$n \times n$</span> square. Then the square is tiled by (possibly disconnected) colored tiles each of the form <span class="math-container">$S \times T$</span> where <span class="math-container">$S,T \subset \{1,\cdots,n\}$</span> and <span class="math-container">$|S|=|T|=i$</span> for some <span class="math-container">$i.$</span> The question then becomes: Given such a tiling by possibly disconnected squares, can the rows and columns be permuted so that the tiling is a squared square. I.E. in each <span class="math-container">$S \times T,$</span> both <span class="math-container">$S$</span> and <span class="math-container">$T$</span> are intervals of size <span class="math-container">$i.$</span></p> <hr> <p>A <span class="math-container">$K_{nn}$</span> decomposition is equivalent to a particular pair <span class="math-container">$\{\mathcal{A},\mathcal{B}\}$</span> where each of <span class="math-container">$\mathcal{A,B}$</span> is a multiset of partitions of <span class="math-container">$n.$</span> Assume first that the decomposition is perfect. Assign each vertex the partition corresponding to the <span class="math-container">$i$</span> such that some <span class="math-container">$K_{ii}$</span> uses that vertex. and let <span class="math-container">$\mathcal{A,B}$</span> be the multisets of partitions corresponding to the two vertex classes. The following properties are satisfied:</p> <ul> <li><p>Among the <span class="math-container">$n$</span> partitions of <span class="math-container">$\mathcal{A}$</span> an integer <span class="math-container">$i$</span> which appears at all appears <span class="math-container">$i$</span> times and similarly for <span class="math-container">$\mathcal{B}.$</span> </p> <ul> <li>Two partitions <span class="math-container">$\alpha,\beta$</span> one each from <span class="math-container">$\mathcal{A,B}$</span> can share at most one member. Equivalently, there is a partial edge coloring of <span class="math-container">$K_n$</span> using Amber and Blue so that two integers appear together in a partition <span class="math-container">$\alpha \in \mathcal{A}$</span> only if the corresponding edge is Amber.</li> </ul></li> </ul> <p>The converse is also true. Given such a pair of multisets of partitions, a <span class="math-container">$K_{n,n}$</span> decomposition is determined. In the case that the decomposition is not perfect, just use <span class="math-container">$c_i$</span> colors for the parts equal to <span class="math-container">$i$</span> to distinguish the various <span class="math-container">$K_{ii}.$</span> </p> <hr> <p>It has been suggested that such pairs of multisets of partitions might be useful as a data structure to search for <span class="math-container">$K_{nn}$</span> decompositions. If so the second requirement would seem to favor partitions into relatively few parts and high repletion numbers. I've elaborated in an answer (really a long comment) on the <a href="http://www.2874565.com/questions/340083/a-specific-collection-of-subgraphs-in-k-70-70">motivating question</a>.</p> http://www.2874565.com/q/341668 1 Digraphs with same number of semiwalks Sirolf http://www.2874565.com/users/9839 2019-09-15T19:06:20Z 2019-09-16T16:05:50Z <p>This is a follow-up question to <a href="http://www.2874565.com/q/341446">Characterisation of walk-equivalent digraphs</a>.</p> <p><strong>Question:</strong> Do there exists two <em>directed</em> graphs <span class="math-container">$G$</span> and <span class="math-container">$H$</span> consisting of the same number (<span class="math-container">$n$</span>) of vertices, such that <span class="math-container">$$tr(w(A_G,A_G^t)\cdot J)=tr(w(A_H,A_H^t)\cdot J) \tag{1}\label{eq:one}$$</span> holds for every word <span class="math-container">$w(x,y)$</span>? Intuitively, this condition states that <span class="math-container">$G$</span> and <span class="math-container">$H$</span> have the same number of semi-walks of a certain type (as described by <span class="math-container">$w(x,y)$</span>), and this for any such type (i.e., any word <span class="math-container">$w(x,y)$</span>).</p> <p>Here, <span class="math-container">$A_G$</span> and <span class="math-container">$A_H$</span> are the adjacency matrices of <span class="math-container">$G$</span> and <span class="math-container">$H$</span>, respectively, <span class="math-container">$J$</span> is the <span class="math-container">$n\times n$</span>-matrix consisting of all ones. For a word <span class="math-container">$w(x,y)$</span>, for example <span class="math-container">$w(x,y)=x.y.x$</span>, <span class="math-container">$w(A_G,A_G^t)$</span> is interpreted as <span class="math-container">$A_G\cdot A_G^t\cdot A_G$</span>.</p> <p><strong>Important restriction:</strong> There should <strong>not</strong> exist a doubly quasi-stochastic matrix <span class="math-container">$S$</span> (a matrix <span class="math-container">$S$</span> such that <span class="math-container">$S.\mathbf{1}=\mathbf{1}$</span> and <span class="math-container">$\mathbf{1}^t\cdot S=\mathbf{1}$</span> with <span class="math-container">$\mathbf{1}$</span> the <span class="math-container">$n\times 1$</span>-vector consisting of all ones.) such that <span class="math-container">$A_G\cdot S=S\cdot A_H$</span>.</p> <p>In the answer <a href="http://www.2874565.com/q/341573">http://www.2874565.com/q/341573</a> to <a href="http://www.2874565.com/q/341446">Characterisation of walk-equivalent digraphs</a> a counter example was given such that <span class="math-container">$tr(A^k\cdot J)=tr(B^k\cdot J)$</span> holds for every <span class="math-container">$k\geq 0$</span>. However, the example does not satisfy the more general condition (\ref{eq:one}).</p> <p><strong>Update:</strong> Note that since <span class="math-container">$A_G\cdot A_G^t$</span> and <span class="math-container">$A_H\cdot A_H^t$</span> are <em>symmetric</em> matrices, and (\ref{eq:one}) implies that <span class="math-container">$tr((A_G\cdot A_G^t)^k\cdot J)=tr((A_H\cdot A_H^t)^k\cdot J)$</span> for any <span class="math-container">$k\geq 0$</span>, these matrices must be related by a doubly quasi-stochastic matrix <span class="math-container">$O$</span>, i.e., <span class="math-container">$A_G\cdot A_G^t\cdot O=O\cdot A_H\cdot A_H^t$</span>. Similarly for the symmetric matrices <span class="math-container">$A_G^t\cdot A_G$</span> and <span class="math-container">$A_H^t\cdot A_H$</span>, possibly with another doubly quasi-stochastic matrix <span class="math-container">$O'$</span>. This <em>severely restricts</em> candidate graphs. Perhaps this helps.</p> http://www.2874565.com/q/341608 3 Generalization of Menger's Theorem to Infinite Graphs Tri http://www.2874565.com/users/51389 2019-09-15T02:12:27Z 2019-09-15T02:12:27Z <p>Aharoni and Berger generalized Menger's Theorem to infinite graphs: For any digraph, and any subsets A and B, there is a family F of disjoint paths from A to B and a set separating B from A consisting of one vertex of each path in F.</p> <p>But what I need is a criterion (at least, a useful sufficient condition) telling me when there is a family of disjoint paths from A to B covering all of A. (I only need it for acyclic digraphs in which every path has at most 3 vertices.) What is known?</p> http://www.2874565.com/q/341578 1 Worst case performance of heuristic for the non-eulerian Windy Postman Problem Manfred Weis http://www.2874565.com/users/31310 2019-09-14T15:28:49Z 2019-09-14T15:28:49Z <p>The Windy Postman Problem seeks the cheapest tour in a complete undirected graph, that traverses each edge at least once; the cost of traversing an edge is positive and may depend on the direction, in which an edge is traversed.<br> It can be assumed that the graph is complete. </p> <p>Zaw Win has proved that the problem is solvable in polynomial time if the graph is eulerian and NP-hard otherwise. </p> <p>Now, as the graph is complete, it is eulerian, iff the number of vertices is odd and a complete non-eulerian graph can be rendered eulerian by removing the edges of a perfect matching, which leads to the following </p> <blockquote> <p><strong>Questions:</strong> </p> <ul> <li>in an optimal solution to a non-eulerian Windy Postman Problem of a complete graph the set of edges that are traversed more than once constitute to a perfect matching and each of those edges is traversed exactly twice? </li> <li>what is the performance of the heuristic of taking as the edges of the perfect matching the ones whose weight-sum over both directions of traversal is minimal and then adding the edges of the shortest euler tour through the other edges?</li> <li>Is the minimum weight matching the best choice of edges to traverse twice?</li> </ul> </blockquote> <p>the rationale behind the heuristic is that the postman would move along the euler tour and whenever a vertex is encountered that is adjacent to matching edge that hasn't been traversed yet, traverse it and return along it again, essentially treating the matching edges as deadend streets. </p> <p>As both parts of the heuristic, determining an optimal general perfect matching and determining the optimal solution to the restriction of the Windy Postman Problem to an eulerian spanner, are polynomial and so is the suggested heuristic.</p> http://www.2874565.com/q/341551 1 Definition of k-partite hypergraph Boonpipop Sirirojrattana http://www.2874565.com/users/145840 2019-09-14T08:15:17Z 2019-09-14T08:44:46Z <p>I would like to know the standard definition of k-partite hypergraph.</p> <p>There are two natural generalizations of k-partite graph to k-partite hypergraph: 1. For all edges e, any two vertices in e are not contained in the same part. (All vertices must come from different parts) 2. For all edges e, all vertices in e are not contained in the same part.</p> <p>I found papers referring to each definition using the same term ¡°k-partite hypergraph¡±. Here is what I wonder: Which one of those is more frequently used? I would like to refer to the second one in my article. Is it acceptable to call the second definition k-partite hypergraph, or is there another term for the second case?</p> <p>Thank you.</p> http://www.2874565.com/q/341493 15 Examples of proofs by making reduction to a finite set [closed] SomeoneHAHA http://www.2874565.com/users/143384 2019-09-13T15:17:31Z 2019-09-23T10:48:34Z <p>This is a very abstract question, I hope this is appropriate.<br> Suppose <span class="math-container">$T$</span> is some claim over some infinite set <span class="math-container">$A$</span>, for example, let <span class="math-container">$A$</span> be the set of all loopless planar graphs, and <span class="math-container">$T$</span> be the claim "for every element <span class="math-container">$a \in A$</span>, the chromatic number of <span class="math-container">$a$</span>'s dual graph is <span class="math-container">$\leq 4$</span>" (this is known as "Four-color Theorem"); or, let <span class="math-container">$A = \mathbb{N}$</span>, and <span class="math-container">$T$</span> be the claim "there are no 3 elements <span class="math-container">$x, y, z \in A$</span> such that <span class="math-container">$x^5 + y^5 =z^5$</span>" (a specific case of Fermat's last theorem).<br> In the first example, it is possible to prove the claim <span class="math-container">$T$</span> by testing some claim <span class="math-container">$T'$</span> over <strong>finite</strong> set <span class="math-container">$A' \subset A$</span>, see <a href="https://en.wikipedia.org/wiki/Four_color_theorem#Proof_by_computer" rel="noreferrer">proof by computer section</a>. This is done by a series of reductions, showing that if all the elements in some finite set satisfy a property, then the (original) claim holds.<br> In some sense, mathematical induction is similar: we test a claim on finite set ("the base case"), then proving <span class="math-container">$a_n \rightarrow a_{n+1}$</span>, which shows the claim is correct for all space. </p> <p>Are there more known cases like that? i.e. proving (a combinatorial) claim by reduction to finite cases? </p> http://www.2874565.com/q/341446 1 Characterisation of walk-equivalent digraphs Sirolf http://www.2874565.com/users/9839 2019-09-12T22:37:17Z 2019-09-14T15:27:41Z <p><strong>Setting</strong> Let <span class="math-container">$G=(V,E)$</span> be an undirected graph. A <em>walk</em> <span class="math-container">$\pi$</span> in <span class="math-container">$G$</span> of length <span class="math-container">$k$</span> is a sequence of <span class="math-container">$k+1$</span> vertices <span class="math-container">$v_1,\ldots,v_{k+1}$</span> such that for each <span class="math-container">$i\in[1,k]$</span>, <span class="math-container">$\{v_i,v_{i+1}\}\in E$</span>. Let <span class="math-container">$H=(W,F)$</span> be another undirected graph having the same number of vertices as <span class="math-container">$G$</span>, i.e., <span class="math-container">$|V|=|W|=n$</span>.</p> <p>If for each <span class="math-container">$k$</span>, <span class="math-container">$G$</span> and <span class="math-container">$H$</span> have the same number of walks of length <span class="math-container">$k$</span>, then it is known that there is matrix <span class="math-container">$Q$</span> such that <span class="math-container">$A_G\cdot Q=Q\cdot A_H$</span>, where <span class="math-container">$A_G$</span> and <span class="math-container">$A_H$</span> denote adjacency matrices of <span class="math-container">$G$</span> and <span class="math-container">$H$</span>, respectively, and such that <span class="math-container">$Q\cdot\mathbf{1}=\mathbf{1}$</span> and <span class="math-container">$\mathbf{1}^t\cdot Q=\mathbf{1}^t$</span>, where <span class="math-container">$\mathbf{1}$</span> is the <span class="math-container">$n\times 1$</span>-vector consisting of all ones. (A matrix with this property is sometimes called doubly quasi-stochastic). The converse also holds, i.e., when <span class="math-container">$A_G\cdot Q=Q\cdot A_H$</span> holds for a doubly quasi-stochastic matrix, then for any <span class="math-container">$k$</span>, <span class="math-container">$G$</span> and <span class="math-container">$H$</span> have the same number of walks of length <span class="math-container">$k$</span>.</p> <p><strong>Question</strong> Let us consider the <em>directed graph</em> (digraph) case. Is there an example of two digraphs with the same number of vertices that have same number of walks of length <span class="math-container">$k$</span>, for any <span class="math-container">$k$</span>, yet there is <strong>no</strong> doubly quasi-stochastic matrix <span class="math-container">$Q$</span> such that <span class="math-container">$A_G\cdot Q=Q\cdot A_H$</span>?</p> http://www.2874565.com/q/340215 0 Graphs "weak" in context of cutting subgraphs NikoWielopolski http://www.2874565.com/users/144145 2019-09-09T17:03:03Z 2019-09-09T17:03:03Z <p>Lately I've been looking into graphs (simple, undirected, finite) that are in some way weak when it comes to connectivity, that is:</p> <hr> <p>Let <span class="math-container">$G$</span> be a graph of order <span class="math-container">$n$</span>. We'll say that <span class="math-container">$G$</span> is <span class="math-container">$k$</span>-weak if for every induced connected subgraph <span class="math-container">$H$</span> of order <span class="math-container">$k$</span>, <span class="math-container">$G \setminus H$</span> is disconnected.</p> <hr> <p>I wish to find a good (or any) characterization of such graphs. It is fairly easy to show that trees are <span class="math-container">$2$</span>-weak iff. every leaf is a neighbour of a vertex of a degree greater than <span class="math-container">$2$</span>, and the condition is necessary for all graphs, but it isn't sufficient in general. However, I haven't been able to find any publications on the topic, even for <span class="math-container">$k=2$</span>. </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>