0
votes
3answers
79 views

Combination Problem Understanding

How many ways can a Doctor go to the Hospital on $5$ days of January (which has $31$ days) such that no two visits are on consecutive days? I think the solution is: $\displaystyle\binom{27}{5}$ But ...
0
votes
1answer
14 views

Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
1
vote
1answer
38 views

Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
0
votes
0answers
12 views

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid?

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid? For a matroid, the codomain of the weight function is $[0,\infty)$, from Wikipedia ...
1
vote
1answer
43 views

Meaning of the characteristic polynomial of a matroid

From wikipedia The characteristic polynomial of a matroid $M$ (which is sometimes called the chromatic polynomial,[29] although it does not count colorings), is defined to be $$ p_M(\lambda) ...
2
votes
2answers
56 views

Equivalent definitions for a coloop?

From wikipedia, in a matroid, An element that belongs to no circuit is called a coloop. Equivalently, an element is a coloop if it belongs to every basis. I wonder why the equivalence? From ...
0
votes
1answer
17 views

How do the dependent sets of a matroid characterize the matroid?

Wikipedia says: The dependent sets of a matroid characterize the matroid completely. The collection of dependent sets has simple properties that may be taken as axioms for a matroid. So I ...
1
vote
1answer
25 views

What kind of set system is defined to have this property?

Let $E$ be a set, and $F \in \mathcal P(E)$ has the following property: For every $x\in E$ and $Y,Z\in F$ with $x\notin Y\cup Z$, there exists $X\in F$ with $(Y\cap Z)\cup\{x\}\subseteq X$. I wonder ...
1
vote
0answers
20 views

A set system generated by a closure operator?

Given a ground set $E$, and a matroid closure operator $\tau$ on $\mathcal P(E)$, we can define a set system $(E,F)$ with $$ F := \{X \in \mathcal P(E): \forall x \in X, x \notin \tau(X-\{x\}) \}$$ ...
1
vote
0answers
20 views

What does “modular” in “modulr functions” mean?

From Wikipedia If $\Omega$ is a set, a submodular function is a set function $f:2^{\Omega}\rightarrow \mathbb{R}$, where $2^\Omega$ denotes the power set of $\Omega$, which satisfies one of the ...
0
votes
0answers
29 views

Two definitions of matroid

From Wikipedia, a finite matroid $M$ is a pair $(E,F)$, where $E$ is a finite set and $F$ is a family of subsets of $E$ either with the following properties: The empty set is in $F$. if $X \in ...
0
votes
0answers
7 views

Rank feasible subset of a greedoid

From Wikipedia, given a greedoid $(E,F)$, with ground set $E$ and the class $F$ of feasible sets, A subset $X$ of $E$ is rank feasible if the largest intersection of $X$ with any feasible set has ...
0
votes
0answers
24 views

Computer program for decomposing a graph into subgraphs?

Obviously there are programs out there that can find perfect matchings. I am interested in finding out if there is a program that can, for instance, tell when graphs like the cube graph $Q_n$, has ...
2
votes
2answers
64 views

Lower bounding the number of children in branching process

Suppose we have a recursive branching process where the number of children is given by $n p$ for parameters $n$ and (probability) $p$. Each child branches $n p$ children (once) and these children ...
3
votes
0answers
76 views

A problem on 0-1 matrices.

Given a 0-1 matrix $A$, is there an efficient way to find all 0-1 vectors $x$ such that $Ax = v$ where the entries of $v$ belong to a set $\{a,b\} \subseteq \mathbb{Z}$ of size $2$? Note that $v$ is ...
0
votes
0answers
47 views

Calculate the Probability for Binary Matrix

Consider a binary matrix of dimension $m\times n$. Suppose the probability of occurrence of 1 is $p$ in any row of the matrix. Each row of the matrix is independent to each other. The all possible ...
0
votes
1answer
32 views

Number of $n$-bit strings that contain from none to $n/2$ zeroes

This is a problem that revolves around symmetry. I recognize that if there is a 4-bit string that it will have 1110 as an answer, but it will also have 0111 as an answer. The thing is, I'm not sure ...
2
votes
0answers
30 views

How do you find a minimum of a function with these tools?

Let's say I can define a group $G$ acting on a set of combinatorial objects $X$ and I have a function $f: X \to \Bbb{N}$ that I want to find a minimum of in $X$. Is there a polynomial time ...
0
votes
0answers
31 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
1
vote
1answer
47 views

Question on Proof that the Fibonacci Word is Sturmian

I am currently reading a text where it is proved that the infinite Fibonacci Word $u$ defined as the limit of the sequence $$ u_n = \varphi^n(0) $$ where the morphism is given by $\varphi(0) = 01, ...
0
votes
1answer
22 views

looking for hypergraph decompositions

there are many thms for/types of graph decompositions. in contrast, am looking for various types of hypergraph decompositions...? also esp interested in graph analogs that translate somehow eg ...
0
votes
1answer
34 views

Constrained disjoint subsets

How to partition $n$ weighted elements into $m$ disjoint subsets such that the sum of weight of all elements in a subset is less than equals to the capacity of $j$th subset ($c_j$) . It is given that ...
2
votes
1answer
37 views

Number of trees of a certain size

Given a branching factor $b$ and a tree height $h$, a complete tree has $\sum_{i=0}^h b^i$ nodes. Define a partial tree as a sub-tree of the complete tree, with the same root. How many such partial ...
0
votes
3answers
72 views

Acyclic graph - source node

How can I prove that a directed acyclic graph has a source node? A node 'a' is called source node if doesn't exists edges like ('b','a').
1
vote
2answers
137 views

Probability that $\frac{n}{2}$ bins are empty [close]

A Bloom filter of length $n$ was built. I have only the first $\frac{n}{2}$ bits of this filter. How will the false positive probability change? For the whole Bloom filter, the false positive ...
3
votes
1answer
61 views

Could every ultimately periodic word $\eta$ factored $\eta = pq^{\omega}$ such that $pq$ is primitive?

An infinite word $\eta$ is called ultimately periodic iff $\eta = pq^{\omega}$ for some $p, q \in X^*$. A word $w \in X^*$ is called primitive iff it is not a power of another word, i.e. it could not ...
2
votes
1answer
64 views

Combinatorics/Task Dependency

Here is a competitive programming question: You have a number of chores to do. You can only do one chore at a time and some of them depend on others. Suppose you have four tasks to complete. For ...
0
votes
0answers
52 views

Lower bound of maximum seating plans

10 people will sit in a row of 10 chairs. How do I calculate how many seating plans can be made, where two seating plan are considered the same if two plans share adjacent quadruples? or How can I ...
2
votes
0answers
70 views

Number of orderings of subset sums

In short: In how many ways can all $2^n$ subset sums of $n$ real numbers $a_1,\ldots, a_n$ be ordered? I am not concerned about the case in which different subsets sum to the same number; you may ...
2
votes
2answers
131 views

Computing all simple paths in a distributive lattice in parallel.

(All arrows point downward.) For the poset $P: 2 < 4, 1 < 3, 1 < 4, 3 < 5$ we get the graph: A linear extension of this poset is $1,2,3,4,5$. "A downset or ideal of a poset $(P, ≤)$ is ...
2
votes
0answers
100 views

How to Enumerate of all simple connected labeled graphs with prescribed degree sequence?

For v=4 vertices, there must be 7 possible graphic sequence (3,3,3,3)(3,3,2,2)(3,2,2,1)(3,1,1,1)(2,2,2,2)(2,2,1,1)(1,1,1,1). From (3,3,3,3), one simple graph(complete) can be found. From(3,3,2,2), 6 ...
2
votes
1answer
125 views

Finding the shortest/“most negative” closed directed trail in a weighted digraph with negative weights

I'm using the following definition of a "closed directed trail": a closed directed trail is a directed cycle in a digraph where all edges are distinct. Note that vertices may be repeated, so long as ...
3
votes
0answers
56 views

Minimizing set intersection/block design

I asked this question on the CS theory stack exchange, but didn't get an answer. Was wondering whether anyone here might have some insight. Thanks in advance for any help. Given 3 parameters $s, r$ ...
1
vote
2answers
307 views

Number of binary strings of length n with k adjacent ones

Consider a space $H_n$ of binary strings of $n$ variables. Let $B(n,k)$ be the set of strings with $k$ ones having also an other one on the right, i.e. $$B(n,k) = \{s \in H_n \, \, \, s.t. \, \, \, ...
2
votes
3answers
57 views

looking for a combinatorial interpretation

given positive integers $n,m$ does the fraction $$ \frac{(nm)!}{n!^mm!} $$ count something? Namely does it correspond to the number of possibilities to do something?
1
vote
2answers
87 views

What's the term for a value x that satisfies the constraint $f(x) = f$ for a function f?

I know that $x$ is called the fixed point of a function $f$ if it satisfies the constraint $f(x) = x$. However, for a function $f$ if there exists some value $x$ such that $f(x) = f$ then what is the ...
3
votes
2answers
1k views

MATLAB code to find distance and eccentricity in graphs

I was trying to find the distances between vertices in graphs. But as the number of vertices are increasing up to 25 vertices or more, its becoming a tedious job for me to calculate $distance$ and ...
2
votes
1answer
104 views

An interesting version of the problem “balls into bins”

Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...
1
vote
1answer
93 views

to find disconnected graphs

We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
1
vote
0answers
36 views

is the $d$-dimensional arrangement of Trees still $NP$-hard?

The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
7
votes
2answers
214 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
1
vote
2answers
79 views

Could graph theory aid in the understanding of comparison sorting algorithms?

I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article. Up to $n=15$, we know how many comparisons between elements one must make to ...
3
votes
1answer
227 views

diameter and radius of a regular graph

I am trying to find the radius and diameter of a regular graph $G$ with $d(v_i) < (n-1)/2$. I know for $d(v) \geq (n-1)/2$, $\rm{diam}(G) \leq 2$ and $\rm{radius}(G)=\rm{diam}(G).$ If we are not ...
2
votes
1answer
60 views

Unique sequences from different sets

I am given $n$ sets with a selection of $m$ elements, such as: $$S = \{\{0\}, \{1, 2, 3\}, \{1, 2, 3\}, \{3\}\}$$ I am trying to calculate the number of unique sequences that contain all elements ...
2
votes
2answers
86 views

eccentricity in vertex transitive graphs

I am trying to prove the following.. If $G$ is a veretx transitive graph, then how can we prove that eccentricity of every vertex is same? Getting no idea from where to start? How to prove the same ...
1
vote
1answer
82 views

Why no cut-vertices or cut edges in a graph where eccentricity is same for all vertices

I need help to prove the following statement. There are no cut-vertices or cut-edges(bridges) in a graph where eccentricity is same for all vertices. I am getting that if the graph contains a ...
3
votes
1answer
79 views

property of complement of a graph

I was working out on a problem. Came out with a result that $C_n$ is self centered graph, its complement is also self centered, infact 2-self-centered. Worked out on other few graphs which are self ...
2
votes
1answer
517 views

Eccentricity of vertices in a graph

This question is related to my last question about regular graphs Eccentricity of vertices in a regular graph. I got the required answer but I am having a doubt. Can we put restriction on number of ...
3
votes
0answers
122 views

Binomial Coefficients optimization

Given n and R, I have to find the minimum value of k such that: $${(2^n)-1 \choose k}\bmod(2^n)==R$$ Where $k = \{0, 1, 2, \dots, 2^n-1\}$ Here ${n \choose k}$ is the binomial coefficient ...
3
votes
2answers
203 views

Eccentricity of vertices in a regular graph

I was just trying to find out the eccentricity of the vertices in regular graphs, given in the link http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html#CRG. Surprisingly, eccentricity is the same ...