# Questions tagged [discrete-mathematics]

Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.

473 questions
Filter by
Sorted by
Tagged with
18 views

### Modal logic S4 system

How to prove in S4 system modal logic that ◇□◇x->◇x? Probably i only need to show that ◇□x->x Any help will be great?
1 vote
43 views

### Distinguishing two distributions with f-divergence

The statistical distance (SD) has been widely used as a 'measure' of the closeness of two distributions $D_1$ and $D_1$. Suppose that the statistical distance (here, total variation with $\ell_1$ norm)...
• 11
1 vote
19 views

### Decomposing large bit mult or exp into smaller bit operations

Imagine a machine that can only hold N-bit values (N-bit uint). The machine can also calculate the 2N-bit result of two operations: mult, exp. The 2N-bit result is stored across 2 N-bit values (high/...
• 11
91 views

• 49
24 views

### Graph with constant edge connectivity that remains connected after edge removals

I have an undirected graph $(V, E)$ with constast edge connectivity $\lambda$. Each edge is sampled independently with probability $min\{1,\frac{c \ln n}{\lambda}\}$ for some $c > 0$. I need to ...
• 149
27 views

### Proving existence of sinkless orientation on graph with minimum degree 2

I am given a graph of minimum degree at least 2 (not necessairly regular). I want to prove that there is a way to orient the edges of G such that each node of G has at least one out-going edge. As a ...
• 149
1 vote
31 views

### Trivial vertex cover in regular graph is 2-approximation Proof

I need to show that in any regular graph, taking all nodes gives a 2-approximation vertex cover. My attempt: I am proving that every $k$-regular graph can be reduced to a 2-regular fully connected ...
• 149
1 vote
29 views

### How do I get the number of cycles in a grid. Is there a formula?

So does anyone know the formula in order to get the number of cycles, I'm not directly asking for the answer but at least someone guides me on how to get a cycle given a grid such as an image above.
• 11
40 views

### Prove there is a matching of size n/2 on a graph with 2n vertices each of degree n

Given underirected $n$-regular graph with $2n$ nodes, I am asked to show it has a matching of size $n/2$. My attempt: At each step I will also remove the edge from the graph that I am adding to the ...
• 149
40 views

### Recursion problem T(n)=3T(n/3)+3n

I just need help solving this problem. I know I'm supposed to be using the Master's Theorem but I don't know where to start
1 vote
28 views

### Find sets which are subsets of the given search set?

The problem is the following: You are given a collection( set, list, whatever ) C of sets, and you are given a search set S. We want to find among all sets in C the ones which are subsets of S. Hence, ...
• 121
64 views

### Is there a quantifier more powerful than the other to determine FOL connector?

So basically we have 2 types of quantifier in first order logic, they are universal quantifier and existential quantifier. Usually we use implies connector(->) when we have universal quantifier in ...
1 vote
95 views

• 364
94 views

• 11
4k views

### Real life examples of *zero* weight edges in graphs

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously. Yet, when I recently read here a question on real life example ...
3k views

### Real life examples of negative weight edges in graphs

I am unable to relate to any real life examples of negative weight edges in graphs. Distances between cities cannot be negative. Time taken to travel from one point to another cannot be negative. ...
• 319
118 views

### discrete optimization problem with a matrix inverse

I'm trying to solve this discrete optimization problem:$\newcommand{\I}{\mathcal{I}}\newcommand{\R}{\mathbb{R}}$ \max_{|\I| \le k} f(\I) \qquad\text{where}\; f(\I) :=x_{\I}^{\top} (\Sigma_{\I})^{-1} ...
59 views

### How can it be proved that two different kinds of dfs unequivocally define a unique tree?

How can it be proved that two different kinds of dfs ( for example let call them inorder and postorder) unequivocally define a ...
35 views

### Why is “For all the simple things you have done to me, there exists one thing that makes me happy” FALSE? Use nested quantifiers to prove your point

I've done my due dilligence and tried to answer this question using every resource I could get. KhanAcademy, NesoAcademy, and Rosen's Discrete Mathematics book. I still can't wrap my head around it. ...
• 1
48 views

### Finding the shortest path with this algorithm

This is a homework question. We want to find the shortest $s$-$t$ path in an undirected weighted graph $G = (V, E)$ with capacities $c_e$ for each edge and positive weights. Let $S'$ be the set of all ...
• 115
20 views

### Polytime Mapping Reduction from Language A to Language A (identity)

How would I create a polytime mapping reduction to prove A ≤p A for any language A. I was thinking to assume A is in P to start. For every 𝑥: 𝑥∈𝐴 iff 𝑓(𝑥)∈𝐴. But I am not sure what to do from ...
1 vote
32 views

### Linear programming and network flow

I would like some hint in this homework question. I have to write the max-flow problem (with souce $s$ and sink $t$) as a linear program. I have to do this by defining variables on each $s - t$ path, ...
1 vote
38 views

### Finding a path that passes through a given vertex

This is a homework question. Let $G = (V, E)$ be an undirected graph. Let $u, v, w \in V$, find a path from $u$ to $w$ that passes through $v$. I know that I can solve this by running BFS on $u$ and ...
1 vote
112 views

### How to get the highest score in this game?

I would like some advice in this homework question. There is a three players game, in which each player ($A, B$, and $C$) is given a $n$-length array of integer values. There are $n$ rounds in this ...
• 115
10 views

### Discrete Event Simulation: modeling entity arrivals

I have seen the stochastic introduction of simulated "entities" (typically queuing for service) via stochastic inter-arrival times. Specifically, the times between arrivals are simulated ...
• 101
77 views

### Longest sequence of 1s in a binary matrix

I would like a hint for this homework question. The problem is to come up with a divide and conquer solution for finding the maximum sequence of 1s in a given a binary matrix of order $n$. The ...
1 vote
42 views

### Assigning balls to bins with constraints

Let $S= \{ b_{11}, b_{12}, b_{21}, b_{22}, b_{31}, b_{32},\dots, b_{n1}, b_{n2} \}$ be a set of $2n$ balls grouped in $n$ pairs, and $T = \{ B_1, B_2, \dots, B_m\}$ be a set of $m$ bins with ...
• 115
Consider an acylicic directed weighted graph in which the nodes represent cities and the weights represent the amount of fuel a car spends when going through that edge. At each city $u$ the car ...
Given a binary square matrix of order $n$. Can the problem of finding the longest sequence of 1's (horizontal or vertical) be solved with recursion? I know how to solve the problem without recursion ...