1
vote
0answers
8 views

Selecting one number from each set with minimum variance

I have a dataset that I need to find several sets of "similar" looking events across many days, which leads to the following problem. Suppose I have $N \sim 500$ sets, each containing $N_j \in [5, ...
0
votes
0answers
15 views

The Whitehouse simplicial complexes and compositional (Lagrange) inversion

Associahedra and Lagrange inversion of ordinary generating functions (OEIS A133437): For an o.g.f $ f(x)= a_1x+a_2x^2 + \cdots$ with inverse $f^{(-1)}(x)= b_1x+b_2x^2 + \cdots$, the compositional ...
2
votes
1answer
17 views

Round table arrrangement for 13 people using graph theory

13 Members of a new club ,meet each day for lunch at a round table. They decide to sit such that every memher has different neighbours at each lunch.How many days can this arrangement last? ...
0
votes
1answer
19 views

number of vertices a special graph

Suppose a tree G has exactly one vertex of degree i for each 2<=i<=m and all other vertices have degree 1. How many vertices does G have?
5
votes
0answers
64 views

Traveling salesman problem: can a terrible strategy beat a good one?

Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
6
votes
1answer
63 views

Traveling salesman problem: a worst case scenario

For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
2
votes
0answers
40 views

Cubic 3-edge connected graph has edge cover that can omit 2/3 of all edges over 5 graphs (so 2/15 per graph) and be 2-edge connected

Let's assume that I have a cubic 3-edge connected simple graph $G$. After taking a perfect matching (and we can specify which one we want), I want to split the remaining edges in 5 sets $U_1, ..., ...
2
votes
1answer
42 views

Algebraic Combinatorics about a Finite Graph

Here is a problem listed on a book 'Algebraic Combinatorics' by Richard P.Stanley. Let $G$ be a finite graph with at least two vertices. Suppose that for some $l \ge 1$, the number of walks of ...
1
vote
1answer
64 views
+50

counting occurence of subgraphs by counting their occurence in larger subgraphs

I have a mental block in fully understanding the following notion. Let $G$ be a graph of order $n$ and $H$ a fixed small graph of order $k \le n$. Suppose that there are $d$ copies of $H$ as an ...
0
votes
1answer
35 views

How to prove the equivalence of 2 affine spaces given that one is the subset of the other one?

For the sake of completeness, I would like to give you some concepts before asking the questions: For every simplex $S=<<x^{0},x^{1},...,x^{k}>>$ in $\Bbb R^{n}$, denote by $H_s$, the ...
0
votes
1answer
67 views

Prove that the graph $H = H_1\cup H_2 = (V_1\cup V_2,E_1\cup E_2)$ is connected.

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
0
votes
1answer
290 views

provide a combinatorial proof that $C_{n+1} = C_0C_n + C_1C_{n-1} + …. + C_kC_{n-k} + …C_nC_0$

(a) Let $C_n$ denote the number of ways of writing a valid list of open and closed parentheses of length $2n$ (valid means that at any point along the list, the number of open parentheses must be ...
0
votes
1answer
30 views

Number of trees on a vertex set $\lbrace{1,2,\ldots,7\rbrace}.$

How many trees are there on the vertex set $\lbrace{1,2,\ldots,7\rbrace}$ in which the vertices $2$ and $3$ have degree 3, and vertex $5$ has degree 2, and all the others have degree 1. I proceeded ...
0
votes
0answers
38 views

Shape with 81 vertices and 810 edges

I have 81 points. Each one of them has to be connected to 20 others, which means there are 810 connections. How many different ways can I arrange each point to be connected to exactly 20 others?
0
votes
1answer
68 views

Prove that if all costs are proportional to distances, then a shortest tour cannot intersect itself.

Prove that if all costs are proportional to distances, then a shortest tour cannot intersect itself. If replacing two of the intersecting edge with two others edge that pairing up with the same ...
0
votes
1answer
28 views

Hall's marriage problem, graph theoretic version

Let $G = ( V,E)$ be a bipartite graph, where $V = V_1 \cup V_2$ , $|V_1| \leq |V_2|$ . For every $A \subseteq V_1$ let $\phi(A) $ be the set of vertices in $V_2$ adjacent to vertices in $A$. By ...
0
votes
1answer
49 views

Combinatoric Graph

Draw a graph whose nodes are the subsets of {a,b,c}, and for which two nodes are adjacent if and only if they are subsets that differ in exactly one element. (a) What is the number of edges and ...
1
vote
1answer
28 views

How many ways can we color a $7$-cycle with $3$ colors so that no three consecutive nodes are of the same color

I have to paint graph We have three colors. The constraint is that there are no three consecutive nodes of the same color. And my idea is: All ways to paint is $3^7$ I'm going to count ...
0
votes
0answers
20 views

Inclusion-wise minimal feedback arc set

How is the term inclusion-wise defined? More precisely, I am trying to get a hold of what an inclusion-wise minimal feedback arc set is. Let $G = (V,E)$ be a (directed) graph. A feedback arc set $F ...
0
votes
4answers
60 views

a 2-regular graph is cyclic or not?

We know the common result : - If every vertex of a graph G has degree at least2, then G contains a cycle. Can I conclude that 2-regular graphs are cycles where degree is exactly two of every vertex? I ...
5
votes
1answer
54 views

Counting graph isomorphisms and entropy

Question: If all graphs on $n$ vertices are given equal probability, what does the induced probability distribution on the graph isomorphism classes look like? Are there any patterns that emerge as ...
0
votes
1answer
27 views

Probabilistic method in coloring of graph

I was reading Noga Alon's Probabilistic Methods and came across this question which I am unable to prove. There is a two-coloring of $K_n$ where $K_n$ is a complete graph of $n$ vertices with at most ...
3
votes
1answer
92 views

Decomposing the Complete Graph into Forests

Which spanning forests can we partition the complete graph $K_n$ into? I am primarily interested in partitions into one fixed isomorphism class of forest. I'm also assuming whatever divisibility ...
1
vote
0answers
23 views

Transforming spanning sub-graphs

I have the following question: Suppose we have a finite graph $G=(V,E)$. Now take two arbitrary spanning sub-graphs, i.e. $G_1 = (V,E_1)$ and $G_2=(V,E_2)$ with $E_1,E_2 \subseteq E$. Suppose we ...
1
vote
0answers
39 views

A combinatorial enumeration problem on graph

Let $G$ be a complete graph of order $n$, we now delete $i$ edges from it, then how many complete subgraphs are there with order $m$ in the rest graph? (You can assume $m\ll n$ and $i\ll m$ if ...
1
vote
1answer
25 views

Graph with small average degree has two vertices of small degree

Suppose $G$ is a graph and its average degree $\epsilon(G) = \frac{2|E(G)|}{|V(G)|}$ is in the interval $0 < \epsilon(G) < 2.$ Then clearly $G$ has one vertex of degree at most $1.$ Reading ...
2
votes
0answers
20 views

Minimum number of transitive paths in tournament

Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if ...
0
votes
0answers
52 views

Kempe chain color swaps in a partially colored map

Crossposted to: http://mathoverflow.net/questions/179340/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using only Kempe chain color swaps (as ...
1
vote
1answer
35 views

proof of Konig's Theorem for bipartite graphs from Menger's Theorem

Could someone provide me with a good reference for a proof of Konig's Theorem for bipartite graphs from Menger's Theorem? Konig's Theorem is as follows: For a bipartite graph $G$, the maximum size ...
-1
votes
1answer
108 views

The union of two connected graphs is connected [closed]

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
1
vote
0answers
19 views

Gallai & Milgram path covers theorem from Diestel

I have a question about the theorem of Gallai and Milgram stating that every directed graph has a path cover $P$ such that one can make an independent set of $G$ by picking vertices from each of the ...
1
vote
0answers
17 views

How many graphs on n nodes, with each component a coherently directed tree

For a positive integer $n$ choose $m$ with $1 \le m \le n$ and let $X$ be a set with $|X|=n$. choose $x_j \in X$ for $j=1,...,m$. Define $m$ directed graphs $X_j$ in the following way: Initially we ...
1
vote
1answer
63 views

counting full bipartite matchings

My actual question is to find the number of transversal given a collection of set ... After a little bit of study it has come down to: How can we count the number of matchings in a bipartite graph ...
3
votes
0answers
44 views

Prove that the number of nonisomorphic ways to partition $E(k_n)$ into complete bipartite graphs at least $2^{n-4}$

Apparently the solution is exercise 1.4.5 in Babal and Frankl's "linear algebra methods in combinatorics (1992)" but it seems they never actually got around to publishing this. Or at least, I am ...
0
votes
0answers
19 views

Number of Strongly Connected Components and Property Testing.

I am working on a problem about the strong connectivity of digraphs. Given graph $\vec G$ that is $k$-$\textit far$ away from being strongly connected (i.e, the minimum number of edges that need to be ...
0
votes
0answers
51 views

Is this composition of $K_{4,4}$ graphs minor-closed?

Following graph is a composition of $K_{4,4}$ bipartite graphs with all the edges are of same length. How do I know whether it is minor-closed or not? The definition in the Wikipedia is as follows. ...
0
votes
0answers
37 views

Number of unique ways to edge-label a complete graph with $k$ distinct labels.

Given $k$ distinct labels, how many unique ways to label the edges of a complete graph with $n$ nodes (nodes are not labeled). For example, to label a complete graph with 3 nodes using 4 distinct ...
1
vote
1answer
33 views

Diameter of a 2-Lift of complete bipartite graph

Give an undirected simple graph $G$ with $n$ vertices and $m$ edges, its 2-Lift is constructed as follows: Define $G_1$ to be the original graph $G$. Make a duplicate copy of $G$ and call it $G_2$. ...
0
votes
1answer
272 views

proof of a theorem in a paper

I was reading a paper named Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths by P. K. Jha (Indian J. pure appl. Math. 23(8): 585-606, August 1992). In one ...
1
vote
0answers
21 views

minimum number of unit distances required for a unit equilateral triangle

Problem. Suppose we have $n$ points on the plane. Among $\binom{n}{2}$ pairwise distances, there are $e$ number of unit distances. Find minimum $e$ ($e$ as a function of $n$) so that there is a ...
1
vote
0answers
34 views

Probability that a subset of a degree-regular graph shares at least a certain number of mutual connections

Consider a set of $n$ vertices of common degree $p$. What is the probability that some subset of $x$ vertices from $n$ share $q$ mutual connections within that group of size $x$? i.e. If we have ...
6
votes
0answers
123 views

Parity of sum of Kronecker deltas in a graph

For some fixed $n\in\mathbb N$ let $G$ be a graph on the vertex set $\{1,\dots,n\}$ with a total number of $k$ edges $e_1,\dots, e_k$. For any vertex colouring $c(i)$ of the graph, $\delta_e$ is ...
9
votes
1answer
145 views

Graph partition that span a third of edges

Given a graph G is easy to see that we have a partition $V=V_1 \cup V_2$ so that $$e(G[V_1])+e(G[V_2])\leq e(G)/2$$. How can we improve this result showing that we can choose $V_i$ such that ...
0
votes
2answers
29 views

How to find a pointset with unique distances

Is there a way to arrange N number of 2D points within a box so that the distances between the points are unique? I have an application where I can measure the distances between points with some ...
2
votes
1answer
18 views

Eccentricity of vertices in a graph when eccentricity of one vertex is given

I have a very basic doubt. If a vertex in any graph has the eccentricity two, then what can be concluded about eccentricities of other vertices in graph. Is the eccentricity of every vertex is less ...
2
votes
0answers
31 views

Counting symmetric binary matrices with constant line-sum

I'm trying to count, as the title suggests, symmetric matrices with entries $0$ or $1$ and constant line-sum $k$. ($0 \leq k \leq n$). If you start listing the number of these on a table you'll get a ...
2
votes
1answer
44 views

Partition of graph with maximal score

Let $G=(V,E)$ be an undirected graph. Suppose that we partition the nodes into groups $C_1,C_2,\ldots,C_k$. The score of group $C_i$ is $E(C_i)/n(C_i)$, where $E(C_i)$ is the number of edges within ...
5
votes
1answer
83 views

The rows continue to be different to each other

In each position of an $n \times n$ matrix there is a number. We know that all the rows of the matrix are different from each other. Show that we can delete a column so that the rows of the matrix ...
1
vote
1answer
44 views

Examples of Matroids

Preparing an exam, I'm looking for examples of matroids and maybe hints or references on proves that they are. (what I already know are representable matroids and graphic matroids)
4
votes
1answer
40 views

Chromatic number of generalized hypercube

It's clear that the chromatic number of $Q_n$ is $2$. But what about the graph $G$ with vertex set ${n}^{(r)}$ where two vertices are adjacent if and only if their coordiantes differ by one? Can't ...